[数据结构与算法]动态规划（一）：线性 DP —— 数字三角形模型

数字三角形

分析

形如以下：

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 IO
    public 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 IO
    public 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 IO
    public 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 IO
    public 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 IO
    public 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 IO
    public 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));
    }
}

创作挑战赛

新人创作奖励来咯，坚持创作打卡瓜分现金大奖