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

标签 java algorithm dynamic-programming

假设我在 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),我需要它的初始状态(这会丢失)。

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

最佳答案

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

enter image description here

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

enter image description here

在哪里

enter image description here

这里 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
    }
}

关于java - 使用动态规划遍历矩阵的最大成本,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32875905/

相关文章:

java - 最多 k 次买卖股票的最大利润 [递归到 DP]

algorithm - 使用动态规划进行插值

java - 为什么在 Graphics 对象上调用 dispose() 会导致 JPanel 不呈现任何组件

java - 在 Java 中如何选择从哪个库导入类?

algorithm - 如何计算两个移动物体之间的最短距离

algorithm - 如何在订单行上按比例分配折扣?

algorithm - NP完全?具有特定约束的图的最佳图嵌入

algorithm - 子集求和算法

java - gwt-maven-plugin 无法编译,因为 "No source code is available for type org.hibernate.validator.constraints.impl.SizeValidatorForString;"

java - 使用 Java 删除 Azure Blob 存储中的文件夹