都是二维
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 102;
int num[maxn][maxn];
int dp[maxn][maxn];
int main()
{
int K,n,m;cin>>K;
while(K--){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>num[i][j];
}
}
memset(dp,0,maxn*maxn);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
dp[i][j] = max(dp[i-1][j],dp[i][j-1])+num[i][j];
}
cout<<dp[n][m]<<endl;
}
return 0;
}
一维dp 二维num
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 102;
int num[maxn][maxn];
int dp[maxn];
int main()
{
int K,n,m;cin>>K;
while(K--){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>num[i][j];
}
}
//memset(dp,0,maxn*4);
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
dp[j] = max(dp[j],dp[j-1])+num[i][j];
}
cout<<dp[m]<<endl;
}
return 0;
}
都是一维
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 102;
int num[maxn];
int dp[maxn];
int main()
{
int K,n,m;cin>>K;
while(K--){
cin>>n>>m;
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>num[j];
}
for(int j=1;j<=m;j++){
dp[j] = max(dp[j],dp[j-1])+num[j];
}
}
cout<<dp[m]<<endl;
}
return 0;
}