【LeetCode-动态规划】最小路径和

题目描述

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

题目链接: https://leetcode-cn.com/problems/minimum-path-sum/

思路1

使用动态规划自顶向下来做。

  • 状态:dp[i][j]表示从左上角到位置(i,j)的最短路径;
  • 状态转移:因为每次只能向下或者向右移动一步,所以dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
  • 特殊情况:因为状态转移公式存在i-1和j-1,所以上面的状态转移公式使用的情况为i>=1, j>=1;当不满足时:
    • 当i==0并且j>0时,dp[i][j] = dp[i][j-1]+grid[i][j];
    • 当j==0并且i>0时,dp[i][j] = dp[i-1][j]+grid[i][j];

代码如下:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty()) return 0;

        int rows = grid.size();
        int cols = grid[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        dp[0][0] = grid[0][0];
        for(int i=0; i<rows; i++){
            for(int j=0; j<cols; j++){
                if(i==0){   // 第0行,没有上一行
                    if(j-1>=0){
                        dp[i][j] = dp[i][j-1] + grid[i][j];
                    }
                }else if(j==0){ // 第0列,没有上一列
                    if(i-1>=0){
                        dp[i][j] = dp[i-1][j] + grid[i][j];
                    }
                }else{
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
        }
        return dp[rows-1][cols-1];
    }
};
  • 时间复杂度:O(mn)
  • 空间复杂度:O(mn)

思路2

使用动态规划自底向上做。
分析过程和上面的过程类似,状态转移方程为dp[i][j] = min(dp[i+1][j], dp[i][j+1]) + grid[i][j],注意边界情况即可。代码如下:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty()) return 0;

        int rows = grid.size();
        int cols = grid[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols, 0));

        for(int i=rows-1; i>=0; i--){
            for(int j=cols-1; j>=0; j--){
                if(i==rows-1){  // 最后一行
                    if(j==cols-1) dp[i][j] = grid[i][j];
                    else dp[i][j] = dp[i][j+1] + grid[i][j];
                }else if(j==cols-1){    // 最后一列
                    if(i==rows-1) dp[i][j] = grid[i][j];
                    else dp[i][j] = dp[i+1][j] + grid[i][j];
                }else{
                    dp[i][j] = min(dp[i+1][j], dp[i][j+1]) + grid[i][j];
                }
            }
        }
        return dp[0][0];
    }
};
  • 时间复杂度:O(mn)
  • 空间复杂度:O(mn)

思路3

在思路2中,不设置dp数组,在原数组上进行动态规划(将思路2中的dp替换为grid即可),这样就可以将空间复杂度降为O(1)。代码如下:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty()) return 0;

        int rows = grid.size();
        int cols = grid[0].size();
        //vector<vector<int>> dp(rows, vector<int>(cols, 0));

        for(int i=rows-1; i>=0; i--){
            for(int j=cols-1; j>=0; j--){
                if(i==rows-1){  // 最后一行
                    if(j==cols-1) grid[i][j] = grid[i][j];
                    else grid[i][j] = grid[i][j+1] + grid[i][j];
                }else if(j==cols-1){    // 最后一列
                    if(i==rows-1) grid[i][j] = grid[i][j];
                    else grid[i][j] = grid[i+1][j] + grid[i][j];
                }else{
                    grid[i][j] = min(grid[i+1][j], grid[i][j+1]) + grid[i][j];
                }
            }
        }
        return grid[0][0];
    }
};
  • 时间复杂度:O(mn)
  • 空间复杂度:O(1)

相关题目

1、三角形路径最小和:https://www.cnblogs.com/flix/p/12747902.html

上一篇:【剑指Offer-画图让抽象问题形象化】面试题29:顺时针打印矩阵


下一篇:leetcode 翻转数组