Leetcode 62.不同路径题解

题目描述

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

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

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

输入示例

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

输入：m = 7, n = 3
输出：28

解题思路

这仍然是一道dp题

先从递归开始

和上一题爬楼梯很类似也是方案总数 只不过这道题换成只能往走或者往下

因此 递归方程式为 dfs(i,j) = dfs(i-1,j)+dfs(i,j-1)

现在来考虑边界条件 首先是 i-1和j-1 i >= 1 j >= 1

当走到底的时候要返回1 用于计数 如果找到了答案 则返回0

因此递归代码为

class Solution {
public:

    int dfs(int i, int j){
        if(i==0 && j == 0){return 0;}
        if(i == 0 || j == 0){return 1;}
        return dfs(i-1,j) + dfs(i,j-1);
    }

    int uniquePaths(int m, int n) {
        if (m== && n == 1){return 1;}
        return dfs(m-1,n-1); // 注意减一
    }
};

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        def dfs(i,j):
            if i == 0 and j == 0:
                return 0
            if i == 0 or j == 0:
                return 1
            return  dfs(i-1,j) + dfs(i,j-1)
        if m == 1 and n == 1: return 1
        return dfs(m-1,n-1) # 注意减一

提交一下 又又又超时了 大量重复计算

现在到记忆化搜索

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if (m == 1 and n == 1): return 1
        @cache
        def dfs(i,j):
            if i == 0 and j == 0:
                return 0
            if i == 0 or j == 0:
                return 1
            return  dfs(i-1,j) + dfs(i,j-1)
        return dfs(m-1,n-1)

class Solution {
public:

    int dp[230][230];

    int dfs(int i, int j){
        if(i == 0 && j == 0){return 0;}
        if(i == 0 || j == 0){return 1;}
        if(dp[i][j] != 0){return dp[i][j];}
        int res = dfs(i-1,j)+ dfs(i,j-1);
        dp[i][j] = res;
        return res;
    }

    int uniquePaths(int m, int n) {
        if(m==1 && n==1){return 1;}
        for (int i = 0; i < 220; i++){
            for(int j = 0; j < 220; j++){
                dp[i][j] = 0;
            }
        }
        return dfs(m-1,n-1);
    }
};

但还是很慢 现在就是要把递归中的递去掉

还是那样 一比一的翻译

dfs(i,j) = dfs(i-1,j)+dfs(i,j-1)
f[i][j] = f[i-1][j]+f[i][j-1]
i == 0 dp[i][0] = 1
j == 0 dp[0][j] = 1

终止条件 不变

以下是最终的代码

示例代码

# 时间复杂度：O(m * n)
# 空间复杂度: O(m * n)
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                dp[i][j] = dp[i-1][j]+dp[i][j-1]
        return dp[m-1][n-1]

// 时间复杂度：O(m * n)
// 空间复杂度: O(m * n)
class Solution {
public:
    int dp[230][230];
    int uniquePaths(int m, int n) {
        for (int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 || j == 0){
                    dp[i][j] = 1;
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

感谢收看