看了y总的思路这道以前觉得很难得DP题现在看起来真的很简单。。。
状态表示+状态计算
找到最后一个“点”,上一个来到这个点的位置只有两种情况,从上到下,或者从左到右
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
int w[N][N];
int f[N][N];
int n,m;
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>>w[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]) + w[i][j];
}
cout<<f[n][m]<<endl;
}
return 0;
}