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?
Note: m and n will be at most 100.
思路：这是一道DP的题，可用(m,n)表示所在的空格的坐标，以左上角为坐标原点，右下角为目的地，f(m,n)表示到达(m,n)点的路径数。点(m,n)可由(m-1,n)向下到达一步和(m,n-1)向右到达一步达到，因此状态转移公式可知：
f(m,n) = f(m-1,n)+f(m,n-1)，m>1 && n>1
f(m,n)=1,m=1 || n=1
f(m,n)=0, m=0||n=0
本题需要注意的是保存中间转移状态的值，不然会超时。
class Solution {
private:
int f[101][101];
int flag = 0;
public:
int uniquePaths(int m, int n) {
if (flag == 0)
{
memset(f,0,sizeof(f));
}
++flag;
if (m == 0 || n == 0)
{
f[0][0] = 0;
return 0;
}
if (m == 1 || n == 1)
{
f[m][n] = 1;
return 1;
}
if (f[m][n] != 0)
{
return f[m][n];
}
f[m][n] = uniquePaths(m-1, n) + uniquePaths(m, n-1);
return f[m][n];
}
};