《从入门到精通：蓝桥杯编程大赛知识点全攻略》（八）-摘花生、地宫取宝
前言
在许多算法问题中，动态规划是一种非常有效的技巧，能够在处理最优化问题时提供显著的性能提升。通过将问题拆解成更小的子问题，并利用已解决的子问题来构建最终解，动态规划能够显著减少计算量。在本文中，我们将通过具体的应用案例，探讨如何使用动态规划来解决“摘花生”和“地宫取宝”这两个经典问题。
摘花生
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
算法思路
主要分析每个位置都是由上一个位置向下走，或者上一个位置向右走；二维整型数组f，其中f[i][j]表示坐标为i、j所获得的最大的花生数；二维整型数组arr来存储花生数。那么下一个位置所获得的最大花生数就是上边的位置和左边的位置两个取最大值加上当前位置的花生数即（Math.max(f[i - 1][j], f[i][j - 1])+arr[i][j]）；最终要求最多能摘取多少花生数，答案就是f[row][col]。
代码如下
import java.io.*;
public class Main {
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(br);
static int N = 105;
static int[][]arr = new int[N][N];
static int[][] f = new int[N][N];
public static void main(String[] args)throws Exception {
int q = nextInt();
while (q-- > 0) {
int row = nextInt();
int col = nextInt();
for(int i = 1; i <= row; i++) {
for(int j = 1; j <= col; j++) {
arr[i][j] = nextInt();
}
}
for(int i = 1; i <= row; i++) {
for(int j = 1; j <= col; j++) {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1])+arr[i][j];
}
}
pw.println(f[row][col]);
}
pw.flush();
}
public static int nextInt()throws Exception{
st.nextToken();
return (int)st.nval;
}
}
地宫取宝
X 国王有一个地宫宝库，是 n×m个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是 k 件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k件宝贝。
输入格式
第一行 3 个整数，n,m,k，含义见题目描述。
接下来 n 行，每行有 m 个整数 Ci 用来描述宝库矩阵每个格子的宝贝价值。
输出格式
输出一个整数，表示正好取 k 个宝贝的行动方案数。
该数字可能很大，输出它对 1000000007 取模的结果。
数据范围
1≤n,m≤50,1≤k≤12,0≤Ci≤12
输入样例1
2 2 2
1 2
2 1
输出样例1
2
输入样例2
2 3 2
1 2 3
2 1 5
14
算法思路
规定只能向下走和向右走，与上述的摘花生问题十分相似，分别为向下走和向右走；规定物品的价值比自己手里的所有物品价值大才可以拿，也可以不拿，相当于物品的价值是递增的，与最长上升子序列相似（详细内容可参考【最长公共子序列（线性dp）-java - CSDN App】）。需要物品的价值来表示所获得的物品的最大值，同时还需要限制物品的个数在k个，综上所述，需要一个四维数组f来表示动态规划数组。4维分别表示物品所在行、所在列、物品的个数、物品的最大价值。因为物品的价值的范围是0~12，我们需要表示不选物品时价值不存在，所以物品的价值变为1 ~13故接收数据时统一加一，这样0就可以表示不选物品的时候的价值。（即起始点第一件物品选f[1][1][1][w[1][1]] = 1;起始点第一件物品不选f[1][1][0][0] = 1;）
二维数组w来存储物品的价值。
分别枚举行i、列、物品的个数u、物品的价值v，然后分别两种情况选和不选。
最后根据枚举的价值，将所有的方案加起来即f[n][m][k][0] 到 f[n][m][k][13] 的总和。
代码如下
import java.io.*;
public class Main {
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(br);
static int N = 55;
static int mod = 1000000007;
static int n,m,k;
static int[][] w = new int[N][N];
static int[][][][] f = new int[N][N][13][14]; // 行 列 件数 价值
public static void main(String[] args)throws Exception {
n = nextInt();
m = nextInt();
k = nextInt();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
w[i][j] = nextInt();
w[i][j]++;
//价值就变成了从1-13，与其它方案做区分，0当作不选择物品的情况
}
}
//起始点第一件物品选
f[1][1][1][w[1][1]] = 1;
//起始点第一件物品不选
f[1][1][0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) {
continue;
}
//枚举拿物品的个数
for (int u = 0; u <= k; u++) {
//枚举取到物品的最大价值
for (int v = 0; v <= 13; v++) {
//不选 向下走
f[i][j][u][v] = (f[i][j][u][v] + f[i - 1][j][u][v]) % mod;
//不选 向右走
f[i][j][u][v] = (f[i][j][u][v] + f[i][j - 1][u][v]) % mod;
//选
if (u > 0 && v == w[i][j]) {
for (int c = 0; c < v; c++) {
f[i][j][u][v] = (f[i][j][u][v] + f[i - 1][j][u - 1][c]) % mod;
f[i][j][u][v] = (f[i][j][u][v] + f[i][j - 1][u - 1][c]) % mod;
}
}
}
}
}
}
int res = 0;
for (int i = 0; i <= 13; i++) {
res = (res + f[n][m][k][i]) % mod;
}
pw.println(res);
pw.flush();
}
public static int nextInt()throws Exception{
st.nextToken();
return (int)st.nval;
}
}
总结
通过这篇博客，我们深入了解了如何使用动态规划解决“摘花生”和“地宫取宝”问题。这两类问题虽然在表面上看似不同，但通过动态规划的思想，都能够高效地求解出最优解。通过分解子问题、状态转移和边界条件的设计，我们不仅能够掌握动态规划的核心思想，还能够提高解决类似问题的能力。希望本篇博客对读者掌握动态规划有所帮助，并能在其他实际问题中加以应用。