问题：
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?
网上的答案基本都是使用动态规划的方式来实现统计，不考虑时间复杂度的话其实有多重方案。
1.分治法
public static int treatment(int x,int y){ if( x==1 || y==1 ) return 1; return treatment(x-1, y)+treatment(x, y-1); }2.回溯法
private static int count = 0; private static void huisu(int x, int y) { track(0, 0, x, y); } private static void track(int cx, int cy, int x, int y) { int[][] arr = new int[x][y]; System.out.print("(" + cx + "," + cy + ")"); if (cx == x - 1 && cy == y - 1) { count++; System.out.println(); return; } if (cx + 1 <= x - 1) { if (arr[cx + 1][cy] != 1) { //判断下一个点没有被走过 track(cx + 1, cy, x, y); } } if (cy + 1 <= y - 1) { if (arr[cx][cy + 1] != 1) track(cx, cy + 1, x, y);//判断下一个点没有被走过 } arr[cx][cy] = 1; // 表示这个点走过 } 3.动态规划
private static int dp(int m, int n) { int[][] dp = new int[m][n]; 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]; }