【动态规划】方格取数 「动态规划之数字三角形模型」

题目

1027. 方格取数 - AcWing题库

---

设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：

某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。

在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

输入格式

第一行为一个整数N，表示 N×N 的方格图。

接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。

行和列编号从 $1$ 开始。

一行“0 0 0”表示结束。

输出格式

输出一个整数，表示两条路径上取得的最大的和。

数据范围

$N \le 10$

输入样例：

8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

输出样例：

67

解题

方法一：动态规划 数字三角形模型

错误思路

为什么不能先走第一次求出最大值并记录最优路径，然后把路径上的点清零后再走第二次最优路线？

因为：第一次走虽然为局部最优但是对第二次走造成了影响，这就导致第二次走是在第一次影响下所能走的局部最优，不具备「无后效性」，因此分开两次走并不是全局最优解。

例如：

0 1 0
2 2 2
1 0 0

这样的测试用例，在第一次走时一定会把所有的 $2$ 都拿完以得到最优路径，第二次走就只能拿到一个 $1$ 了。
而第一次走不追求局部最优解是可以把图中所有数给拿完的。

错误代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 15;
    static int[][] g = new int[N][N], f = new int[N][N];
    static boolean[][] prevs = new boolean[N][N];
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (true) {
            in.nextToken();
            int i = (int) in.nval;
            if (i == 0) break;
            in.nextToken();
            int j = (int) in.nval;
            in.nextToken();
            int x = (int) in.nval;
            g[i][j] = x;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (f[i - 1][j] > f[i][j - 1]) {
                    f[i][j] = f[i - 1][j] + g[i][j];
                    prevs[i][j] = true;
                } else f[i][j] = f[i][j - 1] + g[i][j];
            }
        }
        int ans = f[n][n];
        for (int i = n, j = n; i > 0 && j > 0;) {
            g[i][j] = 0;
            if (prevs[i][j]) --i;
            else --j;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]) + g[i][j];
            }
        }
        System.out.println(ans + f[n][n]);
    }
}

正确思路

在只走一次的题目的基础上延伸，首先考虑用 $f(x_1, y_1, x_2, y_2)$ 表示所有第一次从 $(1, 1)$ 走到 $(x_1, y_1)$ ，第二次从 $(1, 1)$ 走到 $(x_2, y_2)$ 的所有路径中取得数字和的最大值。

在上面的错误思路中我们发现不能分开考虑两次走的路径，所以尝试两次一起走，那么就需要在求最优路径的基础上同时判断「同一个格子不能被重复选择」极了。

由于每次只能向下或向右行走，不能回头，那么只有在两次走到同一步时才有机会选择到同一个格子，也就是说只有在 $x_1+y_1 = x_2+y_2$ 时，两条路径选择的格子才有可能重合，因此可以把路径长度作为 DP 的阶段，每个阶段中，我们同时把两条路径扩展一步（即路径长度加 $1$ ），来进入下一个阶段。

综上所述，使用 $f(k, x_1, x_2)$ 表示所有第一次从 $(1, 1)$ 走到 $(x_1, k - x_1)$ ，第二次从 $(1, 1)$ 走到 $(x_2, k - x_2)$ 的所有路径中取得数字和的最大值，其中 $k = x_1+y_1=x_2+y_2$ 。

于是，动态规划的初始状态为：$f(2, 1, 1)$ ，目标状态为： $f(2n, n, n)$ 。

对于如何判断两次路径选择了同一个方格，由于每个阶段两条路线所选点的横纵坐标和相同，若横坐标相同，则纵坐标必相同，故使用 $x_1 = x_2$ 来判断：

• $x_1 = x_2$ 时，两路线选格相同，只取一次 $g[x_1][y_1]$ 即可。
• $x_1 \ne x_2$ 时，两路线选格不同，$g[x_1][y_1]$ 与 $g[x_2][y_2]$ 都要取到。

总结：

• 状态定义：$f[k][i_1][i_2]$ 表示所有第一次从 $(1, 1)$ 走到 $(i_1, k - i_1)$ ，第二次从 $(1, 1)$ 走到 $(i_2, k - i_2)$ 的所有路径中取得数字和的最大值。

• 状态转移方程：

  $$f[k][i_1][i_2] =\max(\max(f[k - 1][i_1 - 1][i_2 - 1], f[k - 1][i_1][i_2]), \max(f[k - 1][i_1][i_2 - 1], f[k - 1][i_1 - 1][i_2])) + \begin{cases} g[ i_{1}][ k\ -\ i_{1}] & i_{1} \ =\ i_{2}\\ g[ i_{1}][ k\ -\ i_{1}] \ +\ g[ i_{2}][ k\ -\ i_{2}] & i_{1} \ \neq \ i_{2} \end{cases}$$

• 初始状态：$f[2][1][1] = g[1][1]$ 。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 15;
    static int[][] g = new int[N][N];
    static int[][][] f = new int[N * 2][N][N];
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (true) {
            in.nextToken();
            int i = (int) in.nval;
            if (i == 0) break;
            in.nextToken();
            int j = (int) in.nval;
            in.nextToken();
            int x = (int) in.nval;
            g[i][j] = x;
        }
        for (int k = 2; k <= n + n; ++k) {
            for (int i1 = 1; i1 <= n; ++i1) {
                for (int i2 = 1; i2 <= n; ++i2) {
                    int j1 = k - i1, j2 = k - i2;
                    if (j1 < 1 || j1 > n || j2 < 1 || j2 > n) continue;
                    int t = g[i1][j1];
                    if (i1 != i2) t += g[i2][j2];
                    f[k][i1][i2] = Math.max(Math.max(f[k - 1][i1 - 1][i2 - 1], f[k - 1][i1][i2]),
                        Math.max(f[k - 1][i1][i2 - 1], f[k - 1][i1 - 1][i2])) + t;
                }
            }
        }
        System.out.println(f[n * 2][n][n]);
    }
}