A robot is located at the top-left corner of a m x n grid (marked ‘Start‘ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish‘ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

思路：

/*
从左上到右下 只能下或者有 总共有多少种方法。这是一个典型的DP问题，这里记录的遍历dp[i][j]为从左上到达{i,j} 这个位置可能的方法总数，
那么对于dp[i+1][j+1] = dp[i][j+1] + dp[i+1[j];
当然对于边界需要特殊考虑 ，同时需要注意的就是在申请二维空间时  必须让申请的空间比给出的多一个。
*/

int Unique_path(int m,int n)
{
	vector<vector<int> > dp(m+1);
	int i,j;
	for(i=0;i<dp.size();i++)
		dp[i].assign(n+1,0);
	dp[0][0] =1;
	for(i=0;i<dp.size();i++)
	{
		for(j=0;j<dp[0].size();j++)
		{
			if(i!=0 || j!=0)
			{
				if(i==0)
					dp[i][j] = dp[i][j-1];
				else if(j == 0) 
					dp[i][j] = dp[i-1][j];
				else
					dp[i][j] = dp[i][j-1] + dp[i-1][j];
			}
			
		}
	}		
	return dp[m][n];
}
int main()
{
	cout<<Unique_path(3,7)<<endl;
	
	return 0;
}