931. 下降路径最小和

对自己好一点，心情不好的时候，什么都别考虑，去吃自己爱吃的吧。

LC每日一题，参考931. 下降路径最小和。

题目

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 **的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，为和最小的两条下降路径

解题思路

• 记忆化搜索：最容易想到的就是以第一行每个元素开始递归往下找三个分支,每个分支继续递归找三个分支直到最后一行,然后使用记忆化搜索减少重复计算。
• 动态规划：也可反向思考,定义动态规划方程,每行每个元素都有对应的当前最小路径,计算所有最小路径,最后一行的所有最小路径的最小值即为结果。

记忆化搜索

不使用记忆化搜索时间复杂度O(3^n)会超时.

class Solution {
    int[][] memo;
    public int minFallingPathSum(int[][] matrix) {
        //枚举每一行 下一行从三个数里面找值最小的
        int n = matrix.length, ans = Integer.MAX_VALUE;
        //记忆化搜索
        memo = new int[n][n];
        for(int i = 0; i < n; i++) Arrays.fill(memo[i],Integer.MAX_VALUE);
        for(int i = 0; i < n; i++) {
            ans = Math.min(ans,dfs(matrix,0,i));
        }
        return ans;
    }
    int dfs(int[][] matrix,int row,int col) {
        int n = matrix.length, res = Integer.MAX_VALUE;
        if(row == n) return 0;
        if(memo[row][col] != Integer.MAX_VALUE) return memo[row][col];
        if(col-1 >= 0) res = Math.min(res,dfs(matrix,row+1,col-1));
        res = Math.min(res,dfs(matrix,row+1,col));
        if(col+1 < n) res = Math.min(res,dfs(matrix,row+1,col+1));
        return memo[row][col] = matrix[row][col] + res;
    }
}

复杂度分析

• 时间复杂度：O(n^2)，n为矩阵行/列数,记忆化搜索搜索状态个数n^2,单个状态只会计算一次。
• 空间复杂度：O(n^2)，记忆数组空间n^2。

动态规划

对于第二行每个元素的最小路径和与正上一行正上方三个元素有关,其他行同理.

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length,ans = Integer.MAX_VALUE;
        //动态规划dp[i][j] 表示到达i,j坐标时的最小路径和
        int[][] dp = new int[n][n];
        //转移方程 
        for(int i = 0; i < n; i++) dp[0][i] = matrix[0][i];
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < n; j++) {
                //从正上方三个元素选最小
                int res = dp[i-1][j];
                if(j > 0) res = Math.min(res,dp[i-1][j-1]);
                if(j+1 < n) res = Math.min(res,dp[i-1][j+1]);
                dp[i][j] = res + matrix[i][j];
            }
        }
        for(int i = 0; i < n; i++) ans = Math.min(ans,dp[n-1][i]);
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n^2)，双重循环遍历。
• 空间复杂度：O(n^2)，动态规划记忆数组空间n^2。