/****************************
   Name:  Minimum Path Sum
   Date: 02/02/2016
   Author: Hualin Li
   Description: This is the Minimum Path Sum in the C++. 还是DP大法
   做题感想：这道题放在平时很吓人，细想之下已经想到很多可能，似乎不可能用人脑解决。其实套用了
   DP的方法一切都简单了。
   同样的，只需要记住考虑一维情况下如何处理，顺便写出DP方程就解决问题了。
   
   PS：这次又是差一点做到写code调试一气呵成。可能是之前的DP题目都有点相似吧，呵呵。
   
*****************************/
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
     //If grid is empty
     if(grid.empty()||grid[0].empty())
     return 0;
     //To get vector size
	 int m=grid.size();
	 int n=grid[0].size();
	 //To initialize them
	 int dp[m][n];
	 dp[0][0]=grid[0][0];
	 
	 //For the 1-D case
	 for(int i=1;i<n;i++)
		dp[0][i]=dp[0][i-1]+grid[0][i];
	
	 for(int j=1;j<m;j++)
		dp[j][0]=dp[j-1][0]+grid[j][0];
	
     //For the dp equation
	 for(int l=1;l<m;l++)
	 {
		 for(int k=1;k<n;k++)
		 {
			 dp[l][k]=min(dp[l-1][k],dp[l][k-1])+grid[l][k];
		 }		
	 }
	 
	 return dp[m-1][n-1];
    }
};