leetcode62.Unique Paths

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
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
2
3
Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

一个机器人站在下标为（1，1）的起点走向下标为（m，n）的终点。机器人只允许往下走和往右走。问一共有多少条独特的路线？

思路一：Dynamic Programming

通过递归实现计算。根据题目可知，在任何一个方块，一共有两条路径，一条是往下走，一条是往右走，如果任何一条路径能够到达终点，则返回1，否则返回0。 

1
2
3
4
5
6
7
8
9
10
public int uniquePaths(int m, int n) {
    return uniquePaths(1,1,m, n);
}

public int uniquePaths(int currentRow, int currentColumn, int m, int n){
    if(currentRow==m || currentColumn==n){
        return 1;
    }    
    return uniquePaths(currentRow+1, currentColumn, m ,n ) + uniquePaths(currentRow, currentColumn+1, m, n);
}

同样的思路，也可以从终点开始往回计算，如果能够到达起点，则返回1，否则返回0。 

1
2
3
4
5
6
public int uniquePaths2(int m, int n){
    if(m==1 || n==1){
        return 1;
    }
    return uniquePaths2(n-1, m) + uniquePaths2(n, m-1);
}

但是，以上这两种方法都超时了。显然，当我们不需要知道具体路径选项的时候，遍历所有的路径就显得有些累赘且降低性能。

思路二：杨辉三角##

在Dynamic Programming思路的指引下，我们可以尝试将递归的方法改变为循环的方法来解决。这里就运用到了数学中的杨辉三角。很显然，最左侧一行和最顶侧一行的到达路径数都是1，而任何一个非该行列的节点都可以通过左侧节点和上侧节点的路径数相加得到从起点出发到达自己共有的路径数。我们可以利用二维数组来实现叠加。代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int uniquePath3(int m, int n){
    int[][] map = new int[m][n];
    for(int i = 0; i<m;i++){
        map[i][0] = 1;
    }
    for(int j= 0;j<n;j++){
        map[0][j]=1;
    }
    for(int i = 1;i<m;i++){
        for(int j = 1;j<n;j++){
            map[i][j] = map[i-1][j]+map[i][j-1];
        }
    }
    return map[m-1][n-1];
}

思路三： 排列组合

这里运用的是纯数学的思想。根据题目可知，从起点到终点的总步数是一定的，右行或下行的次数也是一定的。我们只需要确定在总部数中哪些步数右行或是哪些步数下行即可知道其对应的路径。这里运用到排列组合的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int uniquePaths4(int m, int n){
    int totalPath = m + n - 2;
    int down = m-1;
    int right = n-1;
    if(down == 0 || right==0){
        return 1;
    }
    int count = Math.min(down, right);
    long result = 1;
    for(int i = 1 ; i<=count ; i++){
        result *= totalPath--;
        result /= i;
    }
    return (int) result;
}