【动态规划】代码随想录算法训练营第三十九天 |62.不同路径,63.不同路径II(待补充)

62.不同路径

1、题目链接:. - 力扣(LeetCode)

2、文章讲解:代码随想录

3、题目:

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

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

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

示例 1:

  • 输入:m = 3, n = 7
  • 输出:28

示例 2:

  • 输入:m = 2, n = 3
  • 输出:3

解释: 从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

示例 3:

  • 输入:m = 7, n = 3
  • 输出:28

示例 4:

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

提示:

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

4、视频讲解:

动态规划中如何初始化很重要!| LeetCode:62.不同路径_哔哩哔哩_bilibili

/**
 * 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
 */
class Solution {
    public 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];

    }
}

63.不同路径II

1、题目链接:. - 力扣(LeetCode)

2、文章讲解:代码随想录

3、题目:

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1:

  • 输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
  • 输出:2 解释:
  • 3x3 网格的正中间有一个障碍物。
  • 从左上角到右下角一共有 2 条不同的路径:
    1. 向右 -> 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右 -> 向右

示例 2:

  • 输入:obstacleGrid = [[0,1],[0,0]]
  • 输出:1

提示:

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1

4、视频链接:

动态规划,这次遇到障碍了| LeetCode:63. 不同路径 II_哔哩哔哩_bilibili

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];
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/446643.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

JavaScript高级Ⅱ(全面版)

接上文 JavaScript高级Ⅰ JavaScript高级Ⅰ(自认为很全面版)-CSDN博客 目录 第2章 DOM编程 2.1 DOM编程概述 2.1.4 案例演示(商品全选) 2.1.5 dom操作内容 代码演示&#xff1a; 运行效果&#xff1a; 2.1.6 dom操作属性 代码演示&#xff1a; 运行效果&#xff1a; 2…

H264/265编码参数2: Profile Level Tier

profile和level profile和level是视频编码中两个很重要的概率&#xff0c;中文一般叫做档次和级别。 在MPEG2标准里边&#xff0c;按不同的压缩比分成五个档次&#xff0c;按视频清晰度分为四个级别&#xff0c;如下图所示&#xff1a; 档次和级别共有 20 种组合&#xff0c;…

2024年【化工自动化控制仪表】考试总结及化工自动化控制仪表作业考试题库

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年【化工自动化控制仪表】考试总结及化工自动化控制仪表作业考试题库&#xff0c;包含化工自动化控制仪表考试总结答案和解析及化工自动化控制仪表作业考试题库练习。安全生产模拟考试一点通结合国家化工自动化控…

day-18 长度最小的子数组

运用队列的思维&#xff0c;求出每种满足题意的子数组长度&#xff0c;最小的即为答案&#xff0c;否则返回0 code class Solution {public int minSubArrayLen(int target, int[] nums) {int l0,r0;int ansInteger.MAX_VALUE;int total0;while(r<nums.length){totalnums[r…

C++:类和对象(三)——拷贝构造函数和运算符重载

目录 一、拷贝构造函数 1.概念 2.特性 二、赋值运算符重载 1.运算符重载 2.赋值运算符重载 &#xff08;1&#xff09;注意的点&#xff1a; &#xff08;2&#xff09;赋值运算符不允许被重载为全局函数&#xff0c;只能重载为类的成员函数 &#xff08;3&#xff09;…

STM32单片机示例:ETH_LAN8742_DHCP_NonOS_Poll_H743

文章目录 目的基础说明关键配置关键代码示例链接总结 目的 以太网是比较常用到的功能&#xff0c;STM32系列单片机使用CubeMX配置使用以太网功能比非常方便。不过对于H7系列来说需要使能 DCache 才能启用LwIP&#xff0c;启用Cache后又会带来一些需要特别注意的事情。这篇文章…

HarBor私有镜像仓库安装部署

环境准备 #>>> redis $ yum -y install redis $ systemctl enable --now redis $ vim /etc/redis.conf modify: bind <ipaddress> $ systemctl restart redis#>>> nfs $ yum -y install nfs-utils $ mkdir -p /data/harbor $ vi /etc/exports /data/h…

简介:CMMI软件能力成熟度集成模型

前言 CMMI是英文Capability Maturity Model Integration的缩写。 CMMI认证简称软件能力成熟度集成模型&#xff0c;是鉴定企业在开发流程化和质量管理上的国际通行标准&#xff0c;全球软件生产标准大都以此为基点&#xff0c;并都努力争取成为CMMI认证队伍中的一分子。 对一个…

动静态库

inode inode用于管理文件属性和内容 一个文件只能有一个inode&#xff0c;一个inode可以对应多个文件名 Linux进程中&#xff0c;打开的每一个文件都有对应的文件inode属性和文件页缓冲区&#xff08;内存和磁盘的缓冲区&#xff09; 软硬链接 硬链接 多个文件指向同一个i…

Gradle模块化最佳实践

一&#xff0c;模块化的原因及意义 模块化是一种将大型的软件系统拆分成相互独立的模块的方法。具有以下优势&#xff1a; 代码复用&#xff1a;不同的模块可以共享相同的代码。这样可以避免重复编写相同的代码&#xff0c;提高开发效率。模块独立性&#xff1a;每个模块都可…

【安装教程】windows下安装Faiss-GPU

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 【安装教程】windows下安装Faiss-GPU 查看安装指令 查看安装指令 登录网站&#xff1a;https://anaconda.org/ &#xff0c; 然后搜索faiss-gpu会进入如下界面&#xff0c;或…

Vue 3中的reactive:响应式状态的全面管理

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

讲解Python3内置模块之json编码解码方法

简介 JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式&#xff0c;它基于ECMAScript的一个子集。 JSON采用完全独立于语言的文本格式&#xff0c;这些特性使JSON成为理想的数据交换格式&#xff0c;易于人阅读和编写&#xff0c;同时也易于机器解析和生成&#…

web前端框架

目前比较火热的几门框架: React React是由Facebook(脸书)开发和创建的开源框架。React 用于开发丰富的用户界面&#xff0c;特别是当您需要构建单页应用程序时。它是最强大的前端框架。 弊端: 您不具备 JavaScript 的实践知识&#xff0c;则建议不要使用 React。同样&#x…

MIT6.828LAB4 (3)

LAB3_Part B: Copy-on-Write Fork 文章目录 LAB3_Part B: Copy-on-Write Fork前言练习8练习9练习10练习11练习12总结 前言 记录一下自己的学习过程 实验内容翻译&#xff1a; https://gitee.com/cherrydance/mit6.828 该翻译仅供参考 练习8 实现sys_env_set_pgfault_upcall系统…

内存映射mmap拓展

第一个是上一篇博客中用mmap实现任意两个进程间相互通信&#xff0c;前几篇博客也用管道实现了进程间通信 这里有个问题&#xff0c;管道是基于缓冲区环形队列的&#xff0c;实验也表明读过的数据不能在读利用命名管道实现任意进程间的通信 那么mmap多个读写操作时会是什么情况…

关于GPU显卡的介绍

一.关于英伟达历代产品架构 显卡是一种计算机硬件设备,也被称为显示适配器或图形处理器。目前的硬件部分主要由主板、芯片、存储器、散热器&#xff08;散热片、风扇&#xff09;等部分。显卡的主要芯片是显卡的主要处理单元。显卡上也有和计算机存储器相似的存储器&#xff0…

Mysql数据库-基本表操作

1.表操作 创建表&#xff1a;CREATE TABLE table_name ( field1 datatype, field2 datatype, field3 datatype ) character set 字符集 collate 校验规则 engine 存储引擎; field 表示列名 datatype 表示列的类型 character set 字符集&#xff0c;如果没有指定字符集&#xff…

python学习笔记------集合(set)

集合定义格式 基本语法&#xff1a; #定义集合字面量 {元素&#xff0c;元素&#xff0c;元素......&#xff0c;元素} #定义集合变量 变量名称{元素&#xff0c;元素&#xff0c;元素......&#xff0c;元素} #定义空集合 变量名称set() #定义集合字面量 {元素&#…

【AI辅助研发】-趋势:大势已来,行业变革

【AI辅助研发】-趋势&#xff1a;大势已来&#xff0c;行业变革 引言 在科技日新月异的今天&#xff0c;人工智能&#xff08;AI&#xff09;技术已逐渐渗透到各行各业&#xff0c;其中软件研发行业更是受益匪浅。AI辅助研发已成为大势所趋&#xff0c;不仅提高了软件开发的效…