Minimum_Path_Sum

/*
Minimum Path Sum
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.
*/
//version2
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        if (grid.size()==0) return 0;
        //initialize the first row and first column of arr[][]. arr[i][j] record the minimum path sum at position[i][j].
        int m=grid.size(), n=grid[0].size();
        int arr[m][n];
        arr[0][0]=grid[0][0];
        for (int i=1; i<n; ++i)
          arr[0][i] = grid[0][i] + arr[0][i-1];
        for (int i=1; i<m; ++i)
          arr[i][0] = grid[i][0] + arr[i-1][0];
        for (int i=1; i<m; ++i)
        {
          for (int j=1; j<n; ++j)
          {
            arr[i][j] = grid[i][j] + min(arr[i-1][j],arr[i][j-1]); 
          }
        }
        return arr[m-1][n-1];
    }
};

REMARK:
1. I first wrote a top down recursion(version1), but it failed to pass the test because Time Limit Exceeded. It is too slow. Then I switched to a bottom up recursion(version2). It's simply and fast.
IDEA: Build a m*n matrix arr[][]. arr[i][j] record the minimum path sum at position[i][j]. Then we have the relationship: arr[i][j] = grid[i][j] + min(arr[i-1][j],arr[i][j-1])

//version1
class Solution {
public:
	//helper function helper(grid,m,n) returns the minimum path sum at position(m,n).
	int helper(vector<vector<int> > &grid,int m, int n)
	{
	  if (m==0&&n==0) return grid[0][0];
	  else if (m==0) return (grid[0][n]+helper(grid,0,n-1));
	  else if (n==0) return (grid[m][0]+helper(grid,m-1,0));
	  else return min(helper(grid,m-1,n)+grid[m][n],helper(grid,m,n-1)+grid[m][n]);
	}

    int minPathSum(vector<vector<int> > &grid) {
        if (grid.size()==0) return 0;
        return helper(grid,grid.size()-1,grid[0].size()-1);
    }
};