题目描述
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。
地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走,不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
输入格式
第一行是一个整数T,代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。
输出格式
对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。
数据范围
1≤T≤100,
1≤R,C≤100,
0≤M≤1000
样例
输入样例:
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例:
8
16
思路一:dp
状态表示
集合:定义f[i][j]为从(1, 1)到达(i, j)的所有方案
属性:最大值
状态转移
(i, j)从(i-1, j)即上方过来
(i, j)从(i, j-1)即左方过来
空间压缩
f[i][j]只需要用到这一层和上一层的f元素,所以可以压缩成滚动数组。在此之上,还可以直接压缩成一维数组。
空间复杂度O(n2)
时间复杂度 O(n^2)
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m,t;
int w[N][N],f[N][N];
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin>>w[i][j];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
cout<<f[n][m]<<'\n';
}
return 0;
}
///DP:空间复杂度O(n)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m,t;
int w[N][N],f[N];
int main()
{
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>>w[i][j];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
f[j]=max(f[j],f[j-1])+w[i][j];
cout<<f[m]<<'\n';
}
return 0;
}
Java代码
//二维
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
while (count-- > 0) {
int m = sc.nextInt(), n = sc.nextInt();
int[][] f = new int[m + 1][n + 1];
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n ; j++) {
f[i][j] = sc.nextInt();
}
}
dp[1][1] = f[1][1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n ; j++) {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + f[i][j];
}
}
System.out.println(dp[m][n]);
}
}
}
//一维
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
while (count-- > 0) {
int m = sc.nextInt(), n = sc.nextInt();
int[][] f = new int[m + 1][n + 1];
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = sc.nextInt();
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[j] = Math.max(dp[j - 1], dp[j]) + f[i][j];
}
}
System.out.println(dp[n]);
}
}
}
思路二:记忆化搜索
记忆化搜索:个人理解就是使用一个数组来存储之前已经搜索过的结果,等用到相应的数组时直接调值即可而不
用重新计算一遍。更直观点就是暴力计算所有状态的最优值,例如计算出状态2的最优值后存储到f[2]中,状态3
的最优值 = 状态2的最优值 + a,这里状态2的最优值直接使用即可。
个人理解的和DP的区别:DP是枚举每一个集合的组成结构,通过状态计算公式慢慢往前推,推出正确答案。而记
忆化搜索是枚举一遍所有的状态,直接暴力计算,只是使用了一个数组存储各个状态的最优值。
摘花生中起点和终点固定,从左上角到右下角。在记忆化搜索中考虑如何实现有两种方式,方法一:当前点到终
点的最大值;方法二:起点到当前点的最大值。
对于两种不同的方式,就是思考当前点的走向的不同,实现的方式还是暴力枚举,只不过将每个点的最优值都存
起来加快速度。
时间复杂度
参考文献
C++ 代码
//从起点到当前点
#include "bits/stdc++.h"
using namespace std;
const int N = 110;
int n, a, b, w[N][N], f[N][N];
int dx[2] = {-1, 0}, dy[2] = {0, -1};
int dp(int x, int y)
{
int &v = f[x][y]; // &除了取地址 还有标识的作用 此处为定义引用v
if (v != -1)
return v;
for (int i = 0; i < 2; i++)
{
int x1 = x + dx[i], y1 = y + dy[i];
if (x1 > 0 && x1 <= a && y1 > 0 && y1 <= b)
v = max(v, dp(x1, y1) + w[x][y]);
}
return v;
}
int main()
{
cin >> n;
while (n--)
{
cin >> a >> b;
for (int i = 1; i <= a; i++)
for (int j = 1; j <= b; j++)
cin >> w[i][j];
memset(f, -1, sizeof f);
f[1][1] = w[1][1];
cout << dp(a, b) << endl;
}
return 0;
}
//摘花生 从当前点到终点
#include "bits/stdc++.h"
using namespace std;
const int N = 110;
int n, a, b, w[N][N], f[N][N];
int dx[2] = {1, 0}, dy[2] = {0, 1};
int dp(int x, int y)
{
int &v = f[x][y];
if (v != -1)
return v;
for (int i = 0; i < 2; i++)
{
int x1 = x + dx[i], y1 = y + dy[i];
if (x1 > 0 && x1 <= a && y1 > 0 && y1 <= b)
v = max(v, dp(x1, y1) + w[x][y]);
}
return v;
}
int main()
{
cin >> n;
while (n--)
{
cin >> a >> b;
for (int i = 1; i <= a; i++)
for (int j = 1; j <= b; j++)
cin >> w[i][j];
memset(f, -1, sizeof f);
f[a][b] = w[a][b];
cout << dp(1, 1) << endl;
}
return 0;
}