代码随想录算法训练营第三十九天 | LeetCode 62. 不同路径、63. 不同路径 II

简介: 代码随想录算法训练营第三十九天 | LeetCode 62. 不同路径、63. 不同路径 II

代码随想录算法训练营第三十九天 | LeetCode 62. 不同路径、63. 不同路径 II

文章链接:不同路径        不同路径II

视频链接:不同路径        不同路径II

1. LeetCode 62. 不同路径

1.1 思路

  1. 本题是个二维矩阵,因此 dp 数组也定义为二维的,这样才能记录每个格的状态。从起始位置(0,0)到终止位置(m,n)
  2. dp 数组及下标的含义:dp[i][j] 的含义表示从(0,0)出发,到(i,j) 有dp[i][j]条不同的路径。
  3. 递推公式:由于只能向下和向右走,因此 dp[i][j]=dp[i-1][j]+dp[i][j-1]。还是和70. 爬楼梯一样,我们求的是方法数,不是步数,因此不用在这前两个位置的基础上+1。
  4. 初始化 dp 数组:因为中间那些格子需要从左方和上方推导出来的,因此左方和上方的格子都要初始化,即第 0 行和第 0 列,都初始化为 1 即可,因为我们只能往右和往下走,想走完第 0 行和第 0 列,只能一直向右和向下,都是 1 种路径
  5. 遍历顺序:从左往右,从上往下。因为需要依赖上方和左方的值
  6. 打印 dp 数组:用于 debug 验证

1.2 代码

//
/**
     * 1. 确定dp数组下标含义 dp[i][j] 到每一个坐标可能的路径种类
     * 2. 递推公式 dp[i][j] = dp[i-1][j] dp[i][j-1]
     * 3. 初始化 dp[i][0]=1 dp[0][i]=1 初始化横竖就可
     * 4. 遍历顺序 一行一行遍历
     * 5. 推导结果 。。。。。。。。
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        //初始化
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 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];
    }

2. LeetCode 63. 不同路径 II

2.1 思路

  1. 本题和62. 不同路径的区别在于,在图上多了个障碍
  2. dp 数组及下标的含义:dp[i][j] 的含义表示从(0,0)出发,到(i,j) 有dp[i][j]条不同的路径。和62. 不同路径基本一样
  3. 递推公式:dp[i][j]=dp[i-1][j]+dp[i][j-1] 也是一样的,但是多了个障碍,有了障碍的位置就不能走了,即 if(obstacleGrid[i][j]==0)再进行递推公式dp[i][j]=dp[i-1][j]+dp[i][j-1]
  4. 初始化 dp 数组:这是和62. 不同路径的最大区别,上面是第 0 行和第 0 列都是全 1,但这里如果在第 0 行(列)某个位置有障碍,那么右(下)方的就不是 1 而是 0 了,因为走不到这个位置,因为是只能往下或者往右走
  5. 遍历顺序:从左往右,从上往下。因为需要依赖上方和左方的值
  6. 打印 dp 数组:用于 debug 验证
  7. 注意这里你没必要在上述基础上遍历 dp 数组时加个条件:如果上面有障碍就只加上左边的,如果左边有障碍的就只加上上边的。这个没必要的。因为在有障碍的地方跳过了不给 dp[i][j] 赋值了,那个位置的 dp[i][j] 是为 0 的,后面即使加上也没事。

2.2 代码

//
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        //如果在起点或终点出现了障碍,直接返回0
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
            return 0;
        }
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
            }
        }
        return dp[m - 1][n - 1];
    }
}
目录
打赏
0
0
1
0
9
分享
相关文章
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
133 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
100 1
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
77 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
102 1
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口