题目描述
Hello Kitty只能向东或向南走,不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
样例
输入样例:
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例:
8
16
算法1 —— 直接做
(暴力枚举) $O(n^2)$
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n, m;
int g[N][N], f[N][N];
int main()
{
int T;
cin >> T;
while (T --)
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
cin >> g[i][j];
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + g[i][j];
// 从上面或者从左边过来
}
cout << f[n][m] << endl;
// 最后结尾就是答案
}
return 0;
}
算法2
优化一下f[N][N]
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + g[i][j];
其中,f[i - 1][j]是上一层的,已经更新过的,而f[i][j - 1]是这一层的,也是已经更新过的。
所以,f[i - 1][j] = f[j],f[i][j - 1] = f[j - 1]
注
f[N] 每次都需要重置0,不然还是会沿用上一轮的数值
时间复杂度 $O(n^2)$
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n, m;
int g[N][N], f[N];
int main()
{
int T;
cin >> T;
while (T --)
{
memset(f, 0, sizeof f); // 每次都需要重置
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
cin >> g[i][j];
f[j] = max(f[j], f[j - 1]) + g[i][j];
}
cout << f[m] << endl;
}
return 0;
}