本文共 1393 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要找到通过给定方形整数数组 A 的下降路径的最小和。下降路径的定义是从第一行的任何元素开始，每一行只能选择一个元素，并且下一行选择的元素与当前行的元素最多只能相隔一列。

方法思路

我们可以使用动态规划来解决这个问题。动态规划的状态转移方程如下：

• dp[i][j] 表示到达数组的第 i 行第 j 列的最小路径和。
• 状态转移：dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1]) + A[i-1][j-1]，其中 dp[i-1][j-1], dp[i-1][j], 和 dp[i-1][j+1] 是从上一行转移来的状态。
• 初始化：第一行的 dp 值直接从数组 A 取得，因为第一行没有上面可以转移。

解决代码

public class Solution {
    public int minFallingPathSum(int[][] A) {
        int n = A.length;
        if (n == 0) return 0;
        int m = A[0].length;
        int[][] dp = new int[n + 1][m + 2];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for (int j = 1; j <= m; j++) {
            dp[1][j] = A[0][j - 1];
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.min(
                    Math.min(dp[i-1][j], dp[i-1][j-1]),
                    dp[i-1][j+1]
                ) + A[i-1][j-1];
            }
        }
        int res = Integer.MAX_VALUE;
        for (int j = 1; j <= m; j++) {
            if (dp[n][j] < res) {
                res = dp[n][j];
            }
        }
        return res;
    }
}

代码解释

这种方法确保了我们在处理每一行和每一列时，都能正确地计算出最小路径和。

转载地址：http://cmfv.baihongyu.com/