java - 使用动态规划遍历矩阵的最大成本

Question

假设我在 Java 中有一个 m x n 矩阵。

我想找出从第一列到最后一列的最大遍历成本。每个值代表发生的成本。我可以在矩阵中向上、向下和向右移动。每个单元只能访问一次。允许从列的顶部单元格到同一列的底部单元格进行转换，反之亦然。

为简单起见，考虑以下矩阵:

2 3 17
4 1 -1
5 0 14

如果我要找出最大成本，我的答案是 46 (2 → 5 → 4 → 1 → 3 → 0 → 14 → 17)。

我尝试使用以下递归关系使用动态方法解决此问题:

maxCost(of destination node) = max{ maxCost(at neighbouring node 1), maxCost(at neighbouring node 2), maxCost(at neighbouring node 3) } + cost(of destination node)

在这种情况下，它会是这样的:

maxCost(17) = max{ maxCost(3), maxCost(-1), maxCost(14) } + 17;

由于每个单元格只能被访问一次，我知道我需要维护一个相应的 m x n isVisited 矩阵。但是，我不知道如何维护 isVisited 矩阵。计算 maxCost(3) 时会修改矩阵；但是对于 maxCost(-1) 和 maxCost(14)，我需要它的初始状态(这会丢失)。

我的方法对这个问题是否正确？另外，我不知道我的函数应该是什么样子。(这是我第一次尝试动态规划)。

Answer 1

这是一个艰难的过程。请注意，由于您的路径不能重复访问过的单元格，因此您可能的路径会有类似“蛇”的行为，例如:

想法是在 f[j][i] 中存储以单元 (j, i) 结束的路径的最大长度。现在假设我们要从 f[j][i-1] 转换到 f[j'][i]。然后，我们可以选择从单元格 (j, i) 直接转到单元格 (j', i) 或者我们可以从单元格 (j , i) 到单元格 (j', i) 通过环绕顶部/底部边缘。因此，f[j][i] 的更新可以计算为:

在哪里

这里 a 是给定的数组。

现在的问题是如何有效地计算 sum(a[j..j'][i]，否则运行时间将是 O(m^3n) . 你可以通过为 sum(a[j..j'][i]) 使用一个临时变量 tmp_sum 来解决这个问题，你增加 j。算法的运行时间将是 O(m^2 n)。

这是一个示例实现:

package stackoverflow;

public class Solver {

    int m, n;
    int[][] a, f;

    public Solver(int[][] a) {
        this.m = a.length;
        this.n = a[0].length;
        this.a = a;
    }

    void solve(int row) {
        f = new int[m][n];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                f[i][j] = Integer.MIN_VALUE;

        for (int i = 0; i < n; ++i) {
            int sum = 0;
            for (int j = 0; j < m; ++j)
                sum += a[j][i];
            for (int j1 = 0; j1 < m; ++j1) {
                int tmp_sum = 0;
                boolean first = true;
                for (int j2 = j1; j2 != j1 || first; j2 = (j2+1)%m) {
                    if (first)
                        first = false;
                    tmp_sum += a[j2][i];
                    int best_sum = Math.max(tmp_sum, sum - tmp_sum +a[j1][i]+a[j2][i]);
                    if (j1 == j2)
                        best_sum = a[j1][i];
                    int prev = 0;
                    if (i > 0)
                        prev = f[j1][i-1];
                    f[j2][i] = Math.max(f[j2][i], best_sum + prev);
                }
            }
        }

        System.out.println(f[row][n-1]);
    }

    public static void main(String[] args) {
        new Solver(new int[][]{{2, 3, 17}, {4, 1, -1}, {5, 0, 14}}).solve(0); //46
        new Solver(new int[][]{{1, 1}, {-1, -1}}).solve(0); //2
    }
}