题解
dp水题,动态转移方程为:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j]
。代表i
行j
列能摘到的花生最大值。
因为我们只需记录上一层的情况,所以可以去掉第一个维度,优化一下空间,时间复杂度仍为$O(n * m)$
#include <bits/stdc++.h>
using namespace std;
int dp[105];
int arr[105][105];
int main() {
int r, c, T;
cin >> T;
while(T--) {
cin >> r >> c;
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++)
cin >> arr[i][j];
for(int i = 1; i <= r; i++) {
for(int j = 1; j <= c; j++)
dp[j] = max(dp[j], dp[j - 1]) + arr[i][j];
}
cout << dp[c] << endl;
memset(dp, 0, sizeof dp);
}
}