dp01

标签：int cin 花生 dp01 include dp

摘花生

题目描述

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
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;
}

标签：int,cin,花生,dp01,include,dp
From： https://www.cnblogs.com/yuanshitianzun123/p/18453255