二维dp和一维dp

解题思路:第i行第j个数只能由第i-1行第j和第j-1的最大值得来;

也就是说进行到第f[i][j]个数时f[i][j]=max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j]);

其实我们也可以观察到上述方程只需要三个数就可以完成

三个变量可以完成的方法我就不多说了

给大家看看一维的怎么来写

f[j]=max(f[j]+a[i][j],f[j-1]+a[i][j]);

注意事项:必须要倒序
如果为正序第f[j]已经更新到第i行了但你算下一个数f[j+1]时其实你要的是第i-1行的数据但f[j]已经更新了导致错误

每次循环重置一下f数组的值
参考代码:

一维的

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int t, n;

int a[105][105];

int f[105];

int main()

{

cin >> t;     //t组数据

for (int m = 1; m <= t; m++)

{

cin >> n;    //有n行数据

for (int k = 1; k <= n; k++)

{

for (int j = 1; j <= k; j++)

{

cin >> a[k][j];     //记录值

}

}//下面才是主要的上面只是输入

for (int i = 1; i <= n; i++)

{

for (int j = n; j >= 1; j--)

{

f[j] = max(f[j] + a[i][j], f[j - 1] + a[i][j]);

}

}

int s=0;//因为只是把最后一行的n个数据给更新成了几条路径的最大值，不确定其中最大的路径是哪个要循环找出最大的

for (int i = 1; i <= n; i++)

{

s = max(f[i], s);

}

cout << s<< endl;

memset(f, 0, sizeof(f));

}

return 0;

}