通过题意可知,来设f[i][j]表示为所有从(1,1)到(i,j)这个点的能取到花生的最大数;
并且题目说只能向东或向南走,也即向右和向下走,也即为从倒数第二步开始进行dp,分别向下和向右。即状态方程为
f[i][j]=max(f[i-1)[j],f[i][j-1])+a[i][j];
代码
while(t--)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max(f[i][j-1],f[i-1][j])+a[i][j];
cout<<f[n][m]<<endl;
}