64. 最小路径和(C++)---动态规划解题

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

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

示例:

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

——题目难度:中等


 

分析

大致思路和63. 不同路径 II(C++)---动态规划解题(并进行滚动数组思想优化)差不多。
用dp[i][j]来表示 坐标(0,0) 到 坐标(i,j) 的数字总和。


-代码如下

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        if (n == 0 && m == 0) return 0;
        
        vector<vector<int>> dp(n, vector<int>(m));
        dp[0][0] = grid[0][0];
        for(int j = 1; j < m; j++) {
        	dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        for(int i = 1; i < n; i++) {
        	dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int i = 1; i < n; i++) {
        	for(int j = 1; j < m; j++) {
        		dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        	}
        }
        
        return dp[n][m];
};

运用「滚动数组思想」优化代码

由于这里 dp[i][j] 只与 dp[i-1][j] 和 dp[i][j-1] 相关
所以可以运用「滚动数组思想」来优化，这里的优化是 “时间换空间”（运行时间变长一些，所用空间变少一些）
其实相当于前一行 往 下一行的状态转移

-下面代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        if (n == 0 && m == 0) return 0;
        
        vector<int> dp(m);
        dp[0] = grid[0][0];
        for(int j = 1; j < m; j++) {
        	dp[j] = dp[j-1] + grid[0][j];
        }
        for(int i = 1; i < n; i++) {
        	dp[0] = dp[0] + grid[i][0];
        	for(int j = 1; j < m; j++) {
        		dp[j] = min(dp[j-1], dp[j]) + grid[i][j];
        	}
        }
        
        return dp[m-1];
    }
};