题目链接
https://www.acwing.com/problem/content/1017/
数字三角形 DP
解题思路
状态表示 : 用 f[i][j] 表示从 (1, 1) 到 (i, j) 摘到最多的花生数量
状态计算 :
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n, m;
int f[N][N], w[N][N];
int main()
{
int t;
cin >> t;
while (t -- )
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> f[i][j];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
f[i][j] += max(f[i - 1][j], f[i][j - 1]);
cout << f[n][m] << endl;
}
return 0;
}