Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

这道题和前面很多题都好像。

解法一：

转态A[i][j]可以表示左上点到grid[i][j]作为右下角的路径的最小和，那么它只依赖于A[i-1][j]和A[i][j-1]。状态转移方程是：
A[i][j]=min{A[i-1][j],A[i][j-1]}+grid[i][j]
需要注意的是边界条件的处理，但是可以将A[i][j]的维数设置的比grid[i][j]的维数大1，这样就可以将边界统一起来了。
时间复杂度是O(M*N),M是矩阵的宽，N是矩阵的高。空间复杂度是O(M*N)。
runtime:28ms

class Solution {
public:
    int minPathSum(vector
   
    >& grid) { int height=grid.size(); int width=grid[0].size(); int current=0; vector
    
      > mask(height+1,vector
     
      (width+1,INT_MAX)); for(int i=0;i
      
     
    
   

解法二：

解法一在空间上是可以做优化的，可以将空间复杂度降低为O(min(M,N))。
因为A[i][j]只依赖于A[i-1][j]和A[i][j-1]，所以可以只使用一个vector来存储即可。
下面是按列进行扫描的算法，代码来自：
https://leetcode.com/discuss/38360/easy-dp-solution-in-c-with-detailed-explanations-o-n-space

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