【题目】

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.

【思路】

设sum[i][j] 到位置（i,j）时路径最小和

状态转移方程：

sum[i][j] = min(sum[i][j-1] ,sum[i-1][j]) + grid[i][j] 

 优化（空间轮转）：

sum[j] = min(sum[j],sum[j-1]) + grid[i][j]

【代码】

/*------------------------------------    *   日期：2015-02-04    *   作者：SJF0115    *   题目: 64.Minimum Path Sum    *   网址：https://oj.leetcode.com/problems/minimum-path-sum/    *   结果：AC    *   来源：LeetCode    *   博客：    ---------------------------------------*/    #include 
    
         #include 
     
          #include 
      
           #include 
       
            using namespace std;    class Solution {    public:        int minPathSum(vector
        
         
           > &grid) { if(grid.empty()){ return 0; }//if int row = grid.size(); int col = grid[0].size(); vector
          
            sum(grid[0]); // 第一行 只能从左边过来 for(int i = 1;i < col;++i){ sum[i] += sum[i-1]; }//for // 动态规划 // sum[j] = min(sum[j],sum[j-1]) + grid[i][j] for(int i = 1;i < row;++i){ sum[0] += grid[i][0]; for(int j = 1;j < col;++j){ sum[j] = min(sum[j],sum[j-1]) + grid[i][j]; }//for }//for return sum[col-1]; } }; int main(){ Solution s; vector
           
            
              > grid = { {1,5,3,7},{2,6,4,1},{5,4,6,5}}; int result = s.minPathSum(grid); // 输出 cout<
             
              <