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?
机器人只能向下和向右走。。走到最后一个位置。求总共多少条路线。这题考察动态规划
1、回溯法。该方法是可以使用的，但是测试的时候，当数字大了以后，会超时。
这是自己写的回溯法，答案是对的。
class Solution { int count=0; public int uniquePaths(int m, int n) { if(m<1&&n<1) return 0; helper(m,n,0,0); return count; } public void helper(int m,int n,int i,int j){ if(i==m-1&&j==n-1){ count++; return ;} if(i<0||j<0) return ; if(i<m-1&&j<n-1){ helper(m,n,i+1,j); helper(m,n,i,j+1); } if(i==m-1) helper(m,n,i,j+1); if(j==n-1) helper(m,n,i+1,j); } }
2.动态规划，机器人每次只能向下或者向右，所以当它到达一个点时，它只有两种可能性：
1），来自上面的点
2），来自左边的点。
我们就可以得到一个公式。假设点(i,j)处的路径数为p[i][j]，则：P[i][j] = P[i - 1][j] + P[i][j - 1].
这里需要处理边界情况,也就是初始化条件，p[0][j]=1,p[i][0]=1.（因为这两个边界只能有一种情况到达）。
class Solution { public int uniquePaths(int m, int n) { int[][] a=new int[m][n]; for(int i=0;i<m;i++) for(int j=0;j<n;j++){ if(i==0||j==0) ///在上边和左边边界处，只有一种路径到达。 a[i][j]=1; else a[i][j]=a[i-1][j]+a[i][j-1]; } return a[m-1][n-1]; } }
3.当然还有一种方法：公式。到终点总共走m+n-2步，其中向下走m-1步，向右走n-1步。现在只要从m+n-2步中选出m-1步就行。二项分布。
int N = n + m - 2;// how much steps we need to do int k = m - 1; // number of steps that need to go down double res = 1; // here we calculate the total possible path number // Combination(N, k) = n! / (k!(n - k)!) // reduce the numerator and denominator and get // C = ( (n - k + 1) * (n - k + 2) * ... * n ) / k! for (int i = 1; i <= k; i++) res = res * (N - k + i) / i; return (int)res;