力扣AC：下降路径最小和II - 路径问题

题目链接

下降路径最小和II

题目描述

实现代码

个人实现代码，未AC，还在找原因：

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int preRowMin = Integer.MAX_VALUE;
        int preRowNextMin = Integer.MAX_VALUE;
        int preRowMinJ = 0;
        for(int j=0; j<n; j++) {
            dp[0][j] = matrix[0][j];
            if(dp[0][j] < preRowMin) {
                preRowMin = dp[0][j];
                preRowMinJ = j;
            } else if(dp[0][j] < preRowNextMin) {
                preRowNextMin = dp[0][j];
            }
        }
        if(m == 1) {
            return preRowMin;
        }
        for(int i=1; i<m; i++) {
            int tempRowMin = Integer.MAX_VALUE;
            int tempRowNextMin = Integer.MAX_VALUE;
            int tempRowMinJ = 0;
            for(int j=0; j<n; j++) {
                if(j == preRowMinJ) {
                    dp[i][j] = preRowNextMin + matrix[i][j];
                } else {
                    dp[i][j] = preRowMin + matrix[i][j];
                }
                if(tempRowMin > dp[i][j]) {
                    tempRowMin = dp[i][j];
                    tempRowMinJ = j;
                } else if(tempRowNextMin > dp[i][j]) {
                    tempRowNextMin = dp[i][j];
                }
            }
            preRowMin = tempRowMin;
            preRowMinJ = tempRowMinJ;
            preRowNextMin = tempRowNextMin;
        }
        return preRowMin;
    }
}

copy别人的代码，已AC：

class Solution {
    int MAX = Integer.MAX_VALUE;
    public int minFallingPathSum(int[][] arr) {
        int n = arr.length;
        int[][] f = new int[n][n];
        // i1 代表最小值列下标，i2 代表次小值列下标
        int i1 = -1, i2 = -1;
        // 先转移第一行
        for (int i = 0; i < n; i++) {
            // 更新动规值
            int val = arr[0][i];
            f[0][i] = val;
            // 更新 i1 和 i2
            if (val < (i1 == -1 ? MAX : f[0][i1])) {
                i2 = i1;
                i1 = i;
            } else if (val < (i2 == -1 ? MAX : f[0][i2])) {
                i2 = i;
            }
        }
        // 再转移剩余行
        for (int i = 1; i < n; i++) {
            // 当前转移第 i 行，使用临时变量保存转移过程中的「最小值列下标」&「次小值列下标」
            int ti1 = -1, ti2 = -1;
            for (int j = 0; j < n; j++) {
                f[i][j] = MAX;
                int val = arr[i][j];
                // 更新动规值
                // 可以选择「最小值」的列选择「最小值」
                if (j != i1) {
                    f[i][j] = f[i - 1][i1] + val;
                // 不能选择「最小值」的列选择「次小值」
                } else {
                    f[i][j] = f[i - 1][i2] + val;
                }
                // 更新 ti1 和 ti2
                if (f[i][j] < (ti1 == -1 ? MAX : f[i][ti1])) {
                    ti2 = ti1;
                    ti1 = j;
                } else if (f[i][j] < (ti2 == -1 ? MAX : f[i][ti2])) {
                    ti2 = j;
                }
            }
            // 使用临时变量更新 i1 和 i2
            i1 = ti1; i2 = ti2;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, f[n-1][i]);
        }
        return ans;
    }
}