【LeetCode】62. 不同路径【DP】/【组合数】

题目链接:https://leetcode-cn.com/problems/unique-paths/

难度:中等

题目描述

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

测试用例

示例 1:

【LeetCode】62. 不同路径【DP】/【组合数】
输入:m = 3, n = 7
输出:28


示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右


示例 3:

输入:m = 7, n = 3
输出:28
示例 4:

输入:m = 3, n = 3
输出:6
 

提示

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

题解

【方法一】:动态规划

时间复杂度:【LeetCode】62. 不同路径【DP】/【组合数】

空间复杂度:【LeetCode】62. 不同路径【DP】/【组合数】

机器人只能向右/向下走,所以若想到达第i行,第j列的位置,只有两种走法:

  • 从第i-1行 第j列向下走一步;
  • 从第i行,第j-1列向右走一步。

如下图:

【LeetCode】62. 不同路径【DP】/【组合数】

那么我们设一个数组map[m, n],其中map[i][j]表示到达第i行第j列位置的路径数量。则有递推公式:【LeetCode】62. 不同路径【DP】/【组合数】。特殊情况,当只有一行或一列时,只有一种路径(即走直线)。

到这里,大家肯定也想到了用递归(代码如下),但是,用递归会有很多重复计算,本人提交试了一下,直接超时。

超时的递归代码:

class Solution {
    public int uniquePaths(int m, int n) {
        return cal(m, n, 0, 0);
    }

    private int cal(int m, int n, int row, int col){
        if (row + 1 == m || col + 1 == n)
            return 1;
        return cal(m, n, row+1, col) + cal(m, n, row, col+1);
    }
}

正确的Java代码:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] map = new int[m+1][n+1];

        for (int i = 1; i <= n; i++) // 第一行初始化为1
            map[1][i]  = 1;
        for (int i = 1; i <= m; i++) // 第一列初始化为1
            map[i][1] = 1;

        for (int i = 2; i <= m; i++)
            for (int j = 2; j <= n; j++)
                map[i][j] = map[i-1][j] + map[i][j-1]; // DP
        
        return map[m][n];
    }
}

【方法二】:组合数

时间复杂度:【LeetCode】62. 不同路径【DP】/【组合数】

空间复杂度:【LeetCode】62. 不同路径【DP】/【组合数】

因为机器人只能向右或向下走,所以到达第(m,n)处,需要向右走n-1步,向下走m-1步,一共走m+n-2步。因此路径的总数,就是从m+n-2步中选择m-1次向下走的方案数,即组合数:

【LeetCode】62. 不同路径【DP】/【组合数】

计算的时候,我们可以使用m和n中最小的一个,更加节省时间。

代码如下:

class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1; // 注意这个地方,用int会溢出
        if (m > n){ // 取m为较小的一个
            int tmp = m;
            m = n;
            n = tmp;
        }
            
        for (int i = n, j = 1; j < m; i++, j++) // 计算组合数
            ans = ans * i / j;
        
        return (int)ans;
    }
}

 

上一篇:62. 不同路径 DP


下一篇:Linux系统编程62 高级IO - 文件锁,lockf()