题意
输入一个三角形，从最顶层的数字开始向左下或向右下走，每条路径都加起来，问和最大的那条路径的和多少。
思路
这算是第二次接触DP，第一次是做leetcode的最长上升子序列问题。 DP在我看来有一点内存换时间的意思 ，就是存储先前已经计算过的路径，然后在接下来的计算中使用。 在这里推荐一篇文章，我觉得把DP讲的非常好，链接：https://blog.csdn.net/baidu_28312631/article/details/47418773
代码
#include <stdio.h>
#define MAXN 10000 + 10
#define N 100 + 10
#define Max(x, y) (x > y ? x : y)
int cache[N][N];
int maxsum[MAXN];
int main() {
int R, i, j;
while(~
scanf(
"%d", &R)) {
for(i =
1; i <= R; i++)
for(j =
1; j <= i; j++)
scanf(
"%d", &cache[i][j]);
for(i =
1; i <= R; i++)
maxsum[i] = cache[R][i];
for(i = R -
1; i >=
1; i--)
for(j =
1; j <= i; j++)
maxsum[j] = Max(maxsum[j], maxsum[j+
1]) + cache[i][j];
printf(
"%d\n", maxsum[
1]);
}
return 0;
}
上面用的是自顶向下的递推计算， 也可以用记忆化搜索的方法。
记忆化搜索其实是递归的一个改写，通过判断这个状态是否已经计算， 计算过直接返回， 没计算则加入递归进行计算，直接返回已经计算的值。
递归写法
int solve(
int i,
int j)
{
return a[i][j] + i == n ?
0 : max(solve(i +
1, j), solve(i +
1, j +
1));
}
这种写法很巧妙的定了边界n。
记忆化搜索
memset(dp, -
1,
sizeof(dp));
int solve(
int i,
int j) {
if (dp[i][j] >=
0)
return dp[i][j];
return dp[i][j] = a[i][j] + (i == n ? max(solve(i +
1, j), solve(i +
1, j +
1)));
}
