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.
思路：典型的动态规划问题。result[i][j]表示(0,0)到(i,j)的最小值。result[i][j]=min(result[i][j-1],result[i-1][j])+grid[i][j];
class Solution { public: int minPathSum(vector<vector<int> > &grid) { int m=grid.size(); int n=grid[0].size(); if(m==0||n==0) return 0; int result[m][n]; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(i==0) { if(j==0) result[i][j]=grid[i][j]; else result[i][j]=result[i][j-1]+grid[i][j]; } else { if(j==0) result[i][j]=result[i-1][j]+grid[i][j]; else result[i][j]=min(result[i-1][j],result[i][j-1])+grid[i][j]; } } } return result[m-1][n-1]; } };
Minimum Path Sum,布布扣,bubuko.com
原文：http://www.cnblogs.com/awy-blog/p/3619800.html