64. 最小路径和
动态规划
初始
路径只能是向下或者向右，所以第一行的元素就是向右递推的值，第一列的元素就是向下递推的值。其他地方的元素，都可以由其上方或者左方的相邻元素移动得到。元素对应的最小路径和等于其上方相邻元素和左方相邻元素二者对应的最小路径和的最小值加上当前元素的值。
dp[i][0]=dp[i−1][0]+grid[i][0]i>0 and j=0
dp[0][j]=dp[0][j−1]+grid[0][j]i=0 and j>0
dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]i>0 and j>0
class Solution { public: int minPathSum(vector<vector<int>> &grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dp(m, vector<int>(n)); dp[0][0] = grid[0][0]; for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (int i = 1; i < n; i++) { dp[0][i] = dp[0][i - 1] + grid[0][i]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])+grid[i][j]; } } return dp[m - 1][n - 1]; } };
时间复杂度：O(mn)
空间复杂度：O(mn)
优化（滚动数组）
class Solution { public: int minPathSum(vector<vector<int>> &grid) { int m = grid.size(); int n = grid[0].size(); vector<int> dp(n); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) { dp[0] = grid[0][0]; } else if (i == 0) { dp[j] = dp[j - 1] + grid[0][j]; } else if (j == 0) { dp[0] = dp[0] + grid[i][0]; } else { dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]; } } } return dp[n - 1]; } };
空间复杂度：O(n)
每次只存储上一行的dp值
