dp01
摘花生
题目描述
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
H只能向东或向南走，不能向西或向北走。问H最多能够摘到多少颗花生。这是AcWing上的一道经典的dp问题
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=120;
int dp[N][N],A[N][N];
int main(){
int n,m,t;
cin>>t;
while(t--){
memset(dp,0,sizeof dp);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
scanf("%d",&A[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
dp[i][j]=A[i][j]+max(dp[i-1][j],dp[i][j-1]);
}
}
cout<<dp[n][m]<<endl;
}
return 0;
}