2023年8月10日每日一题--1289. 下降路径最小和 II

leetcode链接：1289. 下降路径最小和 II

题目分析

方案一

看了一下题解，才发现是最基本的动态规划问题，昨天做01背包问题做蒙了，总想着他很复杂。

class Solution {
    public int minFallingPathSum(int[][] grid) {
        for (int row = 1; row < grid.length; row++) {
            for (int col = 0; col < grid.length; col++) {
                grid[row][col] = grid[row][col] + findMin(row ,col, grid);
            }
        }
        return findMin(grid.length, -1, grid);
    }

    /**
     * 查找上一行中不与此节点在一列的最小值
     * @param row 当前节点所在行
     * @param col 当前节点所在列
     * @param grid 二维矩阵
     * @return 返回最小值
     */
    private int findMin(int row, int col, int[][] grid) {
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < grid.length; i++) {
            if (i == col) continue;
            if (result > grid[row - 1][i]) result = grid[row - 1][i];
        }
        return result;
    }
}

结果

解答成功:
执行耗时:35 ms,击败了40.70% 的Java用户
内存消耗:48.6 MB,击败了74.74% 的Java用户

分析

时间复杂度：
O( n ^ 3 )

空间复杂度：
O( 1 )

官方题解

https://leetcode.cn/problems/minimum-falling-path-sum-ii/solution/xia-jiang-lu-jing-zui-xiao-he-ii-by-leetcode-solut/

方法一：动态规划

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < n; i++) {
            d[0][i] = grid[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (j == k) {
                        continue;
                    }
                    d[i][j] = Math.min(d[i][j], d[i - 1][k] + grid[i][j]);
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            res = Math.min(res, d[n - 1][j]);
        }
        return res;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/minimum-falling-path-sum-ii/solution/xia-jiang-lu-jing-zui-xiao-he-ii-by-leetcode-solut/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：转移过程优化

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int first_min_sum = 0;
        int second_min_sum = 0;
        int first_min_index = -1;
        
        for (int i = 0; i < n; i++) {
            int cur_first_min_sum = Integer.MAX_VALUE;
            int cur_second_min_sum = Integer.MAX_VALUE;
            int cur_first_min_index = -1;
            
            for (int j = 0; j < n; j++) {
                int cur_sum = (j != first_min_index ? first_min_sum : second_min_sum) + grid[i][j];
                if (cur_sum < cur_first_min_sum) {
                    cur_second_min_sum = cur_first_min_sum;
                    cur_first_min_sum = cur_sum;
                    cur_first_min_index = j;
                } else if (cur_sum < cur_second_min_sum) {
                    cur_second_min_sum = cur_sum;
                }
            }
            first_min_sum = cur_first_min_sum;
            second_min_sum = cur_second_min_sum;
            first_min_index = cur_first_min_index;
        }
        return first_min_sum;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/minimum-falling-path-sum-ii/solution/xia-jiang-lu-jing-zui-xiao-he-ii-by-leetcode-solut/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。