GuilinDev

Lc0062

05 August 2008

62 - Unique Paths

原题概述

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 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

1
2
3
4
5
6
7

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

1
2

Input: m = 7, n = 3
Output: 28

题意和分析

要想从start 点到 finish 点，那么，必然经过 h1 或 h2 点，如下图所示：

enter image description here

所以，问题转化为：求 start 点到 h1 点，或到 h2 点的路径中的较小者，这相当于将问题域变小了 1，递归下去，直到问题域变为 1 个点。

使用额外的一个二维数组dp，其中dp[i][j]表示到当前位置不同的走法的个数，然后可以得到递推式为: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

考虑状态压缩， 每次只需要用到上一行当前列，以及前一列当前行的信息，只需要用一个一维数组存上一行的信息即可，然后扫过来依次更替掉上一行对应列的信息即可，一行一行的刷新，因此可以简化为使用一维数组dp。 时间复杂度是O(m*n)，空间复杂度O(n)。

代码

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    //dp[m][n] = dp[m - 1][n] + dp[m][n - 1] 
    public int uniquePaths(int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        }
        int[][] dp = new int[m][n];
        
        
        // 第一行和第一列的初始化，只有1种走法
        for (int k = 0; k < m; k++) {
            dp[k][0] = 1;
        }
        for (int k = 0; k < n; k++) {
            dp[0][k] = 1;
        }
        
        // 对非第一行和非第一列进行填表
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        
        return dp[m - 1][n - 1];
    }
}

考虑状态压缩，滚动列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    //dp[m][n] = dp[m - 1][n] + dp[m][n - 1] 
    public int uniquePaths(int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        }
        int[] dp = new int[n];
        
        dp[0] = 1; // 只记录列，下面的里面循环中每次一列的最顶上初始化为1
        
        for (int i = 0; i < m; i++) {
            /**
             * 1 1 1 1 ..
             * 1 2 3 4 ..
             * 1 3 6 10 ..
             */
            for (int j = 1; j < n; j++) { 
                // dp[j] += dp[j - 1]；
                // 这里的dp[j]相当于从左边复制路径数复制过来
                // 而dp[j - 1]相当于把上面的路径数加过来
                dp[j] += dp[j - 1]; 
            }
        }
        
        return dp[n - 1]; //返回最后一列的最后一个
    }
}

可以想象，考虑状态压缩的情况下，滚动行也是同样的道理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    //dp[m][n] = dp[m - 1][n] + dp[m][n - 1] 
    public int uniquePaths(int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        }
        int[] dp = new int[m];
        
        dp[0] = 1;  //这里就是每次行的最左边在每轮里循环中为1
                
        for (int j = 0; j < n; j++) {
            for (int i = 1; i < m; i++) {
                dp[i] += dp[i - 1]; // 滚动行往下
            }
        }
        
        return dp[m - 1]; // 返回最后一行的最后一个
    }
}

这道题也可以用纯粹的数学的方法来解，求出组合数， 从左上到右下相当于机器人总共走了m + n - 2步，其中m - 1步向下走，n - 1步向右走，那么总共不同的方法个数就相当于在步数里面m - 1和n - 1中较小的那个数的取法，时间复杂度O(min(m, n)，空间复杂度O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int uniquePaths(int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        }
        double dom = 1, dedom = 1;

        //找出m和n中的较小值
        int small = m < n ? m - 1 : n - 1;
        int big = m < n ? n - 1 : m - 1;
        //组合公式求出分子和分母
        for (int i = 1; i <= small; i++) {
            dedom *= i;
            dom *= small + big + 1 - i;
        }
        return (int)(dom / dedom);
    }
}
This site is open source. Improve this page.