题目描述

原题链接：64. 最小路径和

解题思路

（1）回溯法

分别向右或下进行探查

class Solution {
public:int res = INT_MAX;void backtracking(vector>& grid, int x, int y, int pathSum) {// 超出边界，返回if(x >= grid.size() || y >= grid[0].size())           return ;pathSum += grid[x][y];if(x == grid.size() - 1 && y == grid[0].size() - 1) {res = min(res, pathSum);return ;}for(int i = x; i < grid.size(); i++) {for(int j = y; j < grid[0].size(); j++) {backtracking(grid, x + 1, y, pathSum);            backtracking(grid, x, y + 1, pathSum);}}}int minPathSum(vector>& grid) {backtracking(grid, 0, 0, 0);return res;}
};

此方式会超时。

（2）动态规划

对于二维数组求最优解，常用的方式就是递归+备忘录，也就是动态规划，而递归可以用迭代实现。

• 动态规划五步曲：

（1）dp[i][j]： 到达(i, j)处时，最短路径的长度

（2）递推公式： dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]，因为只能往右或下走，因此到达(i, j)处时，只可能有两条路过来，此时就找已有的两条路中最短路径的那一条。

（3）dp数组初始化： dp[i][0]=dp[i−1][0]+grid[i][0]dp[i][0] = dp[i - 1][0] + grid[i][0]dp[i][0]=dp[i−1][0]+grid[i][0]，dp[0][j]=dp[0][j−1]+grid[0][j]dp[0][j] = dp[0][j - 1] + grid[0][j]dp[0][j]=dp[0][j−1]+grid[0][j]，边界上只会有走下来，这一种情况。dp[0][0]=grid[0][0]dp[0][0] = grid[0][0]dp[0][0]=grid[0][0]。

（4）遍历顺序： 从上到下，从左到右，一步一步逼近终点。

（5）举例： （省略）

class Solution {
public:int minPathSum(vector>& grid) {int n = grid.size(), m = grid[0].size();vector> dp(n, vector(m));dp[0][0] = grid[0][0];for(int i = 1; i < n; i++)          dp[i][0] = dp[i - 1][0] + grid[i][0];for(int i = 1; i < m; i++)          dp[0][i] = dp[0][i - 1] + grid[0][i];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 - 1][m - 1];}
};

参考文章：64. 最小路径和、最小路径和、动态规划之最小路径和