/****************************
   Name:  Unique Paths I 
   Date: 02/01/2016
   Author: Hualin Li
   Description: This is the Unique Paths I in the C++. 还是DP大法
   做题感想：这道题和走楼梯有着异曲同工之妙。解题的诀窍在于列出DP公式如下：
   dp[i][j]=dp[i][j-1]+dp[i-1][j]。同时，要理解一点:如果该路径变成一维的，
   无论是横看的一维还是竖着看的一维，都只有一种走法。
   
*****************************/
class Solution {
public:
    int uniquePaths(int m, int n) {
        
		int dp[m][n];
		
		//initialize both 1-D array
			for(int i=0;i<m;i++)
			dp[i][0]=1;
		
			for(int j=0;j<n;j++)
			dp[0][j]=1;
			
		
		for(int i=1;i<m;i++)
			for(int j=1;j<n;j++)
				dp[i][j]=dp[i][j-1]+dp[i-1][j];
			
		return dp[m-1][n-1];
		
    }
};