跳转至

62 不同路径

深搜(超时)

从左上(1,1)开始往下遍历,函数调用图和二叉树非常相似

重复大量无用节点

这棵树的深度其实就是m+n-1(深度按从1开始计算)。

那二叉树的节点个数就是$ 2^(m + n - 1) - 1$。可以理解深搜的算法就是遍历了整个满二叉树(其实没有遍历整个满二叉树,只是近似而已)

所以上面深搜代码的时间复杂度为\(O(2^{m + n - 1} - 1)\),可以看出,这是指数级别的时间复杂度,是非常大的。

class Solution {
private:
    int dfs(int i, int j, int m, int n){
        if(i > m || j > n)  return 0;
        if(i == m && j == n)    return 1;
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }
public:
    int uniquePaths(int m, int n) {
        return dfs(1, 1, m, n);
    }
};

动态规划

两维做法

初始化dp[i][0] = 1和dp[0][j] = 1

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        // 由于机器人每次只能往下或往右
        // 所以dp[i][0]和dp[0][j]只有一条路
        for(int i = 0; i < m; i++) dp[i][0] = 1;
        for(int j = 0; j < n; j++) dp[0][j] = 1;
        // 从dp[i][j]开始,路径来源可以是dp[i - 1][j]和dp[i][j - 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];
    }
};

时间复杂度:O(m × n)

空间复杂度:O(m × n)

一维优化

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];分析这一递推公式,我们能够发现:在从上到下,从左到右的递归顺序下:

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];的效果和dp[j] = dp[j] + dp[j - 1];相同,因为dp[j]保存的就是dp[i - 1][j]的值,dp[j - 1]保存的就是dp[i][j - 1]的值,更新dp[j]之后dp[j]就变成了dp[i][j]

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 0);
        // 由于机器人每次只能往下或往右
        // 所以dp[i][0]和dp[0][j]只有一条路
        for(int j = 0; j < n; j++) dp[j] = 1;
        // 从dp[i][j]开始,路径来源可以是dp[i - 1][j]和dp[i][j - 1]
        for(int i = 1; i < m; i++){
            // 这里从j = 0开始或者j = 1开始都可以,因为没有条件能够更改dp[i][0]的状态
            for(int j = 1; j < n; j++){
                    dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }
};

时间复杂度:O(m × n)

空间复杂度:O(n)

数论做法

一共\(m - 1 + n -1 = n + m -2\)步,选择其中m - 1步往下,得到组合数就是题解:\(C_{n + m - 2}^{m - 1}\)

见https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html#%E6%80%9D%E8%B7%AF