http://poj.org/problem?id=1163
1、普通递归
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define __max(a,b) (((a) > (b)) ? (a) : (b))
#define MAXNUM 101
int N;
int aMax[MAXNUM][MAXNUM]; // aMax is memorandum
int matrix[MAXNUM][MAXNUM];
int Max(int i, int j)
{
if (i == N)
return matrix[i][j];
return __max( Max(i + 1, j), Max(i + 1, j + 1) ) + matrix[i][j];
}
void Input(int _matrix[MAXNUM][MAXNUM]) // the 2nd dimension must be given!
{
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++)
cin >> _matrix[i][j];
}
}
int main(void)
{
freopen("cin.txt", "r", stdin);
cin >> N;
memset(aMax, -1, sizeof(aMax)); // 0xff
memset(matrix, -1, sizeof(matrix));
Input(matrix);
cout << Max(1, 1) << endl;
return 0;
}
2、记忆式搜索(动态规划)
int Max(int i, int j)
{
if (i == N)
return matrix[i][j];
if (aMax[i + 1][j] == -1)
aMax[i + 1][j] = Max(i + 1, j);
if (aMax[i + 1][j + 1] == -1)
aMax[i + 1][j + 1] = Max(i + 1, j + 1);
return __max( aMax[i + 1][j], aMax[i + 1][j + 1] ) + matrix[i][j];
}
3、方法2的代码优化
int Max(int i, int j)
{
if (i == N)
return matrix[i][j];
if (aMax[i][j] == -1) // 在普通递归的程序中加上
aMax[i][j] = __max( Max(i + 1, j), Max(i + 1, j + 1) ) + matrix[i][j]; // 改
return aMax[i][j]; // 加
}
分享到:
相关推荐
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
poj.grids.cn题型汇总 Dp状态设计与方程总结 1.不完全状态记录 青蛙过河问题 利用区间dp 2.背包类问题 ...<1> 0-1背包,经典问题 ...无限背包,经典问题 ...判定性背包问题 ...数字三角形问题 漂亮的打印
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
放炮问题,北大网站 POJ 1185 算法
POJ1321棋盘问题 很好两种解法很值得去参考一下 完整的实验报告还有代码希望kan
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
北大POJ3411-Paid Roads【class】 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
O(nlogn)凸包问题 poj2187
poj分类poj分类poj分类poj分类
北大POJ1004-Financial Management 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
2遍dp poj_3613解题报告 poj_3613解题报告