数字三角形

分析

形如以下：

7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

状态表示：

• g(i, j) 表示点 (i, j) 的值

• f(i, j) 表示从最下层走到点 (i, j) 的所有路线中的最大值（所以f(0, 0) 才是最后答案）

状态转移：

• 从正下方转移：f(i + 1, j) + g(i, j)
• 从右下方转移：f(i + 1, j + 1) + g(i, j)

状态计算：取最大值 max

代码

import java.util.*;public class Main {public static int dp(int[][] g) {int n = g.length, m = n + 1;int[][] f = new int[n][m];// 最后一层无法从更下面一层转移for (int j = 0; j < m; j++) {f[n - 1][j] = g[n - 1][j];}// 一般情况for (int i = n - 2; i >= 0; i--) {for (int j = 0; j < i + 1; j++) {f[i][j] = Math.max(f[i + 1][j], f[i + 1][j + 1]) + g[i][j];}}return f[0][0];}// for IOpublic static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[][] g = new int[n][n + 1];for (int i = 0; i < n; i++) {for (int j = 0; j < i + 1; j++) {g[i][j] = scanner.nextInt();}}System.out.println(dp(g));}
}

摘花生

分析

状态表示：

• g(i, j) 表示在点 (i, j) 上的花生数量

• f(i, j) 表示从点 (0, 0) 到点 (i, j) 采摘到的最多的花生数量

状态转移：

• 从上边走下来：f(i - 1, j) + g(i, j)
• 从左边走过来：f(i, j - 1) + g(i, j)

状态计算：取最大值 max

代码

import java.util.*;public class Main {public static int dp(int[][] g) {int n = g.length, m = g[0].length;int[][] f = new int[n][m];// 起点无法从任何地方转移过来f[0][0] = g[0][0];// f(i, 0) 只能从上边转移过来for (int i = 1; i < n; i++) {f[i][0] = f[i - 1][0] + g[i][0];}// f(0, j) 只能从左边转移过来for (int j = 1; j < m; j++) {f[0][j] = f[0][j - 1] + g[0][j];}// 一般情况for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]) + g[i][j];}}return f[n - 1][m - 1];}// for IOpublic static void main(String[] args) {Scanner scanner = new Scanner(System.in);int t = scanner.nextInt();while (t-- > 0) {int R = scanner.nextInt();int C = scanner.nextInt();int[][] g = new int[R][C];for (int i = 0; i < R; i++) {for (int j = 0; j < C; j++) {g[i][j] = scanner.nextInt();}}System.out.println(dp(g));}}
}

最低通行费

分析

状态表示：

• g(i, j) 表示穿过点 (i, j) 需要的费用
• f(i, j) 表示从点 (0, 0) 开始直到穿过点 (i, j) 所累计的最小费用

状态转移

• 从上边走下来：f(i - 1, j) + g(i, j)
• 从左边走过来：f(i, j - 1) + g(i, j)

题目要求必须在 2N - 1 的时间内走完，也就是说只能直接往出口走，不能回头。

状态计算：取最小值 min

代码

import java.util.*;public class Main {public static int dp(int[][] g) {int n = g.length, m = g[0].length;int[][] f = new int[n][m];// 因为要取最小值，所以初始状态设为正无穷for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {f[i][j] = Integer.MAX_VALUE;}}// (0, 0) 点无法从任何地方转移过来f[0][0] = g[0][0];// (i, 0) 点只能从上边转移过来for (int i = 1; i < n; i++) {f[i][0] = f[i - 1][0] + g[i][0];}// (0, j) 点只能从左边转移过来for (int j = 1; j < m; j++) {f[0][j] = f[0][j - 1] + g[0][j];}// 一般情况for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + g[i][j];}}return f[n - 1][m - 1];}// for IOpublic static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[][] g = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {g[i][j] = scanner.nextInt();}}System.out.println(dp(g));}
}

方格取数

四维 DP

分析

状态表示

• g(i, j) 表示在 (i, j) 上的值

• f(a, b, c, d) 表示第一次从 (0, 0) 到 (a, b) 与第二次从 (0, 0) 到 (c, d) 之和的最大值

状态转移

• 第一次从上边走下来，第二次从上边走下来：f(a - 1, b, c - 1, d)
• 第一次从上边走下来，第二次从左边走过来：f(a - 1, b, c, d - 1)
• 第一次从左边走过来，第二次从上边走下来：f(a, b - 1, c - 1, d)
• 第一次从左边走过来，第二次从左边走过来：f(a, b - 1, c, d - 1)
• 因为取一次就变 0，所以要判断第一次和第二次是否走过同一个格子

状态计算：取最大值 max

代码

import java.util.*;public class Main {public static int dp(int[][] g) {int n = g.length;int[][][][] f = new int[n][n][n][n];// 起点没法从其他地方转移f[0][0][0][0] = g[0][0];// 一般情况for (int a = 1; a < n; a++) {for (int b = 1; b < n; b++) {for (int c = 1; c < n; c++) {for (int d = 1; d < n; d++) {int x = Math.max(f[a - 1][b][c - 1][d], f[a - 1][b][c][d - 1]);int y = Math.max(f[a][b - 1][c - 1][d], f[a][b - 1][c][d - 1]);int z = g[a][b] + ((a == c && b == d) ? 0 : g[c][d]); // 是否走同一个格子f[a][b][c][d] = Math.max(x, y) + z;}}}}return f[n - 1][n - 1][n - 1][n - 1];}// for IOpublic static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt() + 1;int[][] g = new int[n + 1][n + 1];while (true) {int i = scanner.nextInt();int j = scanner.nextInt();int x = scanner.nextInt();if (i == 0 && j == 0 && x == 0) break;g[i][j] = x;}System.out.println(dp(g));}
}

三维 DP

分析

问题转换：

• 一个人走两次，每个格子拿一次 -> 两个人同时走一次，同个格子拿一次，不同格子分别拿

• 设 A 在 (a, b) B 在 (c, d)，因为俩人同时走，所以 a + b = c + d

• 设 k = a + b = c + d，只要枚举 k、a、c，b 和 d 就定下来了

状态表示

• g(i, j) 表示在 (i, j) 上的值

• f(k, i, j) 表示 A、B 同时走了 k 步，A 从 (0, 0) 走到 (i, k - i) B 从 (0, 0) 走到 (j, k - j) 之和的最大值

状态转移

• A 从上边走下来，B 从上边走下来：f(k - 1, i - 1, j - 1)
• A 从上边走下来，B 从左边走过来：f(k - 1, i - 1, j)
• A 从左边走过来，B 从上边走下来：f(k - 1, i, j - 1)
• A 从左边走过来，B 从左边走过来：f(k - 1, i, j)
• 同个格子拿一次，不同格子分别拿

状态计算：取最大值 max

代码

import java.util.*;public class Main {public static int dp(int[][] g) {int n = g.length;int[][][] f = new int[2 * n][n][n];// 起点没法从其他地方转移f[0][0][0] = g[0][0];for (int k = 1; k < 2 * n; k++) {for (int i = 1; i < n; i++) {for (int j = 1; j < n; j++) {if (k - i >= 0 && k - i < n && k - j >= 0 && k - j < n) {int x = Math.max(f[k - 1][i - 1][j - 1], f[k - 1][i - 1][j]);int y = Math.max(f[k - 1][i][j - 1], f[k - 1][i][j]);int z = g[i][k - i] + (i == j ? 0 : g[j][k - j]);f[k][i][j] = Math.max(x, y) + z;}}}}return f[2 * n - 2][n - 1][n - 1];}// for IOpublic static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt() + 1;int[][] g = new int[n][n];while (true) {int i = scanner.nextInt();int j = scanner.nextInt();int x = scanner.nextInt();if (i == 0 && j == 0 && x == 0) break;g[i][j] = x;}System.out.println(dp(g));}
}

传纸条

分析

问题转换：

• A 从左上到左下，B 从左下到左上，传递者不能是同一人，好感度最高 -> A 和 B 一起从左上到左下，传递者好感度变为 0，好感度最高
• 设 A 在 (a, b) B 在 (c, d)，因为俩人同时走，所以 a + b = c + d
• 设 k = a + b = c + d，只要枚举 k、a、c，b 和 d 就定下来了

状态表示：

• g(i, j) 表示在 (i, j) 上的值
• f(k, i, j) 表示 A、B 同时走了 k 步，A 从 (0, 0) 走到 (i, k - i) B 从 (0, 0) 走到 (j, k - j) （除去起点和终点）之和的最大值

状态转移：

• A 从上边走下来，B 从上边走下来：f(k - 1, i - 1, j - 1)
• A 从上边走下来，B 从左边走过来：f(k - 1, i - 1, j)
• A 从左边走过来，B 从上边走下来：f(k - 1, i, j - 1)
• A 从左边走过来，B 从左边走过来：f(k - 1, i, j)
• 传递者不能是同一人，i != j && k - i != k - j，化简后为 i != j

状态计算：取最大值 max

代码

import java.util.*;public class Main {public static int dp(int[][] g) {int n = g.length, m = g[0].length;int[][][] f = new int[n + m + 2][n + 1][n + 1];// 一般情况for (int k = 1; k <= n + m; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (k - i > 0 && k - i <= m && k - j > 0 && k - j <= m) {int x = Math.max(f[k - 1][i - 1][j - 1], f[k - 1][i - 1][j]);int y = Math.max(f[k - 1][i][j - 1], f[k - 1][i][j]);int z = g[i - 1][k - i - 1] + (i == j ? 0 : g[j - 1][k - j - 1]);f[k][i][j] = Math.max(x, y) + z;}}}}return f[n + m][n][n];}// for IOpublic static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] g = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {g[i][j] = scanner.nextInt();}}System.out.println(dp(g));}
}