AcWing 1015. 摘花生
原题链接
简单
算法1
二维DP
时间复杂度 $O(n^2)$
空间复杂度 $O(n^2)$
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N][N];
int main(){
int T;
cin >> T;
while (T--){
int n,m;
cin >> n >> m;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++){
cin >> f[i][j];
// 边读入边处理
f[i][j] += max(f[i-1][j],f[i][j-1]);
}
cout << f[n][m]<<endl;
}
return 0;
}
算法2
滚动数组
时间复杂度 $O(n^2)$
空间复杂度 $O(n)$
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N],x;
int main(){
int T;
cin >> T;
while (T--){
int n,m;
cin >> n >> m;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++){
cin >> x;
f[j] = max(f[j],f[j-1]) + x;
}
cout << f[m] << endl;
memset(f,0,sizeof f);
}
return 0;
}