AcWing 1015. 摘花生（二维dp）

题目
题意： 从[1][1]走到[r][c] 所能得到的最大花生数量。
关键：f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
f[i][j] 可能从当前位置的上或左到达，所以计算出两者的最大值即可

与01 dp 的区别是，01 只关心选或不选，而这个是从两个方位到达的。

答案：

#include<iostream>
#include<cstdio>
#include<algorithm>
 using namespace std;
  
 const int N=110;

int T,r,c,w[N][N],f[N][N];

int main()
{
	cin>>T;
	while(T--)
	{
		cin>>r>>c;
		for(int i=1;i<=r;i++)
			for(int j=1;j<=c;j++)
			{
				scanf("%d",&w[i][j]);
			}
		for(int i=1;i<=r;i++)
			for(int j=1;j<=c;j++)
			{
			 	f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j]; //f[i][j] 可能从当前位置的上或左到达，所以计算出两者的最大值即可 
			}
		cout<<f[r][c]<<endl;	 
	}
	return 0;
}