# 【算法】机器人到达终点有几条路径？

## 问题：

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.回溯法

`````` public static int test3(int x, int y) {
// 回溯 机器人走迷宫
int left = x - 1, right = y - 1;
int count = huisu(0, 0, left, right);
return count;
}

public static int huisu(int x, int y, int left, int right) {
int count = 0;

if (x == left && y == left) {
return ++count;
}

if (x + 1 <= left) {
x++;
count += huisu(x, y, left, right);
x--; // 回溯条件
}

if (y + 1 <= right) {
y++;
count += huisu(x, y, left, right);
}

return count;
}``````

### 3.动态规划

``````private static int dp(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i] = 1;
}
for (int j = 0; j < n; j++) {
dp[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];

}``````