64、最小路径和

leetcode

Created At : 2020-07-26 00:19

Count:643 Views 👀 :

示例:
代码
1. 暴力递归求解——超时
2. 动态规划

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7

解释: 因为路径 1→3→1→1→1 的总和最小。

代码

暴力递归求解——超时

class Solution {
    // 递归函数
    public int calculate(int[][] grid,int i,int j) {
        if (i == grid.length || j == grid[0].length) return Integer.MAX_VALUE;
        if (i == grid.length - 1 && j == grid[0].length - 1) return grid[i][j];
        return grid[i][j] + Math.min(calculate(grid,i + 1,j),calculate(grid,i,j+1));
    }
    
    public int minPathSum(int[][] grid) {
        return calculate(grid,0,0);
    }
}

动态规划

二维数组存储状态

class Solution {
    // 动态规划思想 
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        
        for (int i = m - 1;i >= 0;i--){
            for (int j = n - 1;j >= 0;j--) {
                if (i == m - 1 && j != n - 1) {
                    dp[i][j] = grid[i][j] + dp[i][j+1];
                } else if (j == n - 1 && i != m - 1) {
                    dp[i][j] = grid[i][j] + dp[i+1][j];
                } else if(j != n - 1 && i != m - 1) {
                    dp[i][j] = grid[i][j] + Math.min(dp[i][j+1],dp[i+1][j]);
                } else {
                    dp[i][j] = grid[i][j];
                }
            }
        }
        
        return dp[0][0];
    }
}

一维数组存储状态

class Solution {
    
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];
        for (int i = m - 1;i >= 0;i--){
            for (int j = n - 1;j >= 0;j--) {
                if (i == m - 1 && j != n - 1) {
                    dp[j] = grid[i][j] + dp[j+1];
                } else if (j == n - 1 && i != m - 1) {
                    dp[j] = grid[i][j] + dp[j];
                } else if(j != n - 1 && i != m - 1) {
                    dp[j] = grid[i][j] + Math.min(dp[j+1],dp[j]);
                } else {
                    dp[j] = grid[i][j];
                }
            }
        }
        
        return dp[0];
    }
}

用原数组本身存储状态，降低空间复杂度

class Solution {
    
    public int minPathSum(int[][] grid) {
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                if(i == grid.length - 1 && j != grid[0].length - 1)
                    grid[i][j] = grid[i][j] +  grid[i][j + 1];
                else if(j == grid[0].length - 1 && i != grid.length - 1)
                    grid[i][j] = grid[i][j] + grid[i + 1][j];
                else if(j != grid[0].length - 1 && i != grid.length - 1)
                    grid[i][j] = grid[i][j] + Math.min(grid[i + 1][j],grid[i][j + 1]);
            }
        }
        return grid[0][0];

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

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com