算法day39|62，63

62.不同路径


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for i in range(n)] for j in range(m)]
        #grid[i][i]指的是在i行i列的有几条路径
        #初始化
        for i in range(m): dp[i][0] = 1
        for i in range(n): dp[0][i] = 1
        #递归表达式
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i][j-1]+dp[i-1][j]
        return dp[m-1][n-1]

创建dp数组，使用列表推导式创建

初始化的时候，需要把第一行和第一列都变成1，因为都只有一条路径

然后还需要注意，m，n到底是行还是列。

遍历顺序也是从前到后

返回最后的m-1/n-1

代码随想录

视频讲解：动态规划中如何初始化很重要！| LeetCode：62.不同路径_哔哩哔哩_bilibili

二刷（ac）


var uniquePaths = function(m, n) {
    //dp[m][n] 意味着在点mn有unique path dp[m][n]
    //递归逻辑
    let dp = new Array(m).fill(1).map(()=>new Array(n).fill(1))
    for(let i = 1;i<m;i++){
        for(let j = 1;j<n;j++){
            dp[i][j] = dp[i-1][j]+dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
    
};

63. 不同路径 II


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        #因为题目没有直接给出行为多少，列为多少
        #行
        m = len(obstacleGrid)
        #列
        n = len(obstacleGrid[0])
        #如果起始点，种植点都出现了障碍物，那么返回0
        if obstacleGrid[0][0]:
            return 0
        if obstacleGrid[m-1][n-1]:
            return 0
            
        dp = [[0 for i in range(n)]for i in range(m)]
        #初始值
        for i in range(m):
            if obstacleGrid[i][0] == 1:
                break
            dp[i][0] = 1
        for i in range(n):
            if obstacleGrid[0][i] == 1:
                break
            dp[0][i] = 1
        #遍历顺序
        for i in range(1,m):
            for j in range(1,n):
                #行列
                #递归公式
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i-1][j]+dp[i][j-1]
        #打印
        return dp[m-1][n-1]

https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html

视频讲解：|动态规划，这次遇到障碍了| LeetCode：63. 不同路径 II_哔哩哔哩_bilibili

看到障碍物就跳过

二刷(未ac，烦死了，卡了好久)


var uniquePathsWithObstacles = function (obstacleGrid) {
    let m = obstacleGrid.length
    let n = obstacleGrid[0].length
    let dp = new Array(m).fill(0).map(() => new Array(n).fill(0))
    if (obstacleGrid[m - 1][n - 1] === 1 || obstacleGrid[0][0] === 1) { return 0 }
    //初始化
    // 只有当为0时，才用往下走
    for (let i = 0; i < m && obstacleGrid[i][0] === 0; i++) {
        //如果有障碍的时候，后面的路径都为0
        dp[i][0] = 1
    }
    for (let i = 0; i < n && obstacleGrid[0][i] === 0; i++) {
        //如果有障碍的时候，后面的路径都为0
        dp[0][i] = 1
    }
    console.log(dp)
 
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 1) continue;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
 
};

相关阅读:
米贸搜| Facebook账号类型看这一篇就足够了
组合数与莫队——组合数前缀和
【Linux】自己实现一个bash进程
并发容器详解
HCNP Routing&Switching之链路聚合
函数式编程-Stream流
Linux下安装oracle11.2.0.4
Java如何实现统计在线人数的功能？
Android C++系列：Linux进程间关系
Understanding JSON Schema

原文地址：https://blog.csdn.net/weixin_42173016/article/details/128163913