【算法挨揍日记】day19——62. 不同路径、63. 不同路径 II

 62. 不同路径 

62. 不同路径

题目描述: 

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

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

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

 解题思路:

状态表示:dp[i][j]表示在到达(i,j)位置后,路线的总数

状态转移方程:

dp[i][j]=dp[i-1][j]+dp[i][j-1];

初始化:

因为我们从(1,1位置开始遍历,我们要保证1,1位置的值要为1),因此我们需要将(0,1)位置设为1,来满足状态转移方程

填表顺序:左到右

返回值:dp【m】【n】

解题代码:

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        dp[0][1]=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][n];
    }
};

63. 不同路径 II

63. 不同路径 II

题目描述:

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

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

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

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

解题思路:

状态表示: dp[i][j]在到达(i,j)后,路线的总数

状态转移方程:当ob(i-1,j-1)等于0的时候,如果向下向右的可以的话,ob(i-1,j-1)就为0,为1的话就没有意义了

初始化:

dp【0】【1】=1

填表顺序:从左到右

返回值:dp【m】【n】;

解题代码: 

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int len1=obstacleGrid.size();
        int len2=obstacleGrid[0].size();
        vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));
        dp[0][1]=1;
        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                if(obstacleGrid[i-1][j-1]==0)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[len1][len2];
    }
};

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

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

相关文章

14.1 Linux 并发与竞争

一、并发与竞争 并发&#xff1a;多个执行单元同时、并行执行。 竞争&#xff1a;并发的执行单元同时访问共享资源(硬件资源和软件上的全局变量等)易导致竞态。 二、原子操作 1. 原子操作简介 原子操作&#xff1a;不能再进一步分割的操作&#xff0c;一般用于变量或位操作。 …

AI:53-基于机器学习的字母识别

🚀 本文选自专栏:AI领域专栏 从基础到实践,深入了解算法、案例和最新趋势。无论你是初学者还是经验丰富的数据科学家,通过案例和项目实践,掌握核心概念和实用技能。每篇案例都包含代码实例,详细讲解供大家学习。 📌📌📌本专栏包含以下学习方向: 机器学习、深度学…

latex自定义缩写

Latex 写文章可能常用到一些缩写&#xff0c;如&#xff1a; .e.g.i.e.cf.etc.w.r.t.i.i.d.et al. 其中有些要斜体&#xff0c;如果每次都要用 \textit{...}、{\it ...} 弄斜&#xff0c;有点麻烦。CVPR 模板中有定义一些命令&#xff0c;可以更方便地输入这些缩写。这里记录…

linux中if条件判断,case...esac,function学习

第一、 if [ 判断式 ] ; then fi 注意&#xff1a;中括号和判断式之间的空格&#xff0c;否则会报错&#xff0c;上案例 第二个图的12行&#xff0c;中括号和条件判断如果没有空格&#xff0c;则会提示缺号‘】’&#xff0c;如第二个图最上面的提示。所以使用中括号的格式…

AI:59-基于深度学习的行人重识别

🚀 本文选自专栏:AI领域专栏 从基础到实践,深入了解算法、案例和最新趋势。无论你是初学者还是经验丰富的数据科学家,通过案例和项目实践,掌握核心概念和实用技能。每篇案例都包含代码实例,详细讲解供大家学习。 📌📌📌在这个漫长的过程,中途遇到了不少问题,但是…

系列十二、过滤器 vs 拦截器

一、过滤器 vs 拦截器 1.1、区别 &#xff08;1&#xff09;触发时机不一样&#xff0c;过滤器是在请求进入容器后Servlet之前进行预处理的&#xff0c;请求结束返回也是&#xff0c;是在Servlet处理完后&#xff0c;返回给前端之前&#xff1b; &#xff08;2&#xff09;过滤…

TCP三次握手和四次挥手

文章目录 TCP三次握手TCP四次挥手 TCP三次握手 三次握手主要是保证连接是双工的&#xff0c;可靠主要是保证重传机制的 客户端发送建立连接的请求&#xff0c;SYN置1&#xff0c;携带一个序号seq服务端接收客户端建立连接的请求后发送一个响应&#xff0c;SYN置1&#xff0c;A…

[BUUCTF NewStar 2023] week5 Crypto/pwn

最后一周几个有难度的题 Crypto last_signin 也是个板子题&#xff0c;不过有些人存的板子没到&#xff0c;所以感觉有难度&#xff0c;毕竟这板子也不是咱自己能写出来的。 给了部分p, p是1024位给了922-101位差两头。 from Crypto.Util.number import * flag b?e 655…

闯关打卡小程序的效果如何

闯关打卡是一种以任务关卡为基础的打卡模式&#xff0c;管理员可配置活动任务关卡&#xff0c;成员加入任务后需依次解锁&#xff0c;打卡完成任务&#xff0c;像闯关游戏一样完成所有任务。 通过打卡活动聚集一群有共同目标、兴趣的人&#xff0c;通过打卡的方式促进共同目标…

python 命令行界面的用户交互

背景 说一千&#xff0c;道一万&#xff0c;程序是为用户服务的&#xff0c;所以在程序运行过程&#xff0c;与用户交互以获取用户的信息输入和决策确认&#xff0c;是无法避免的编程需要考虑和解决的需求。 一个简单的demo 如下的程序中&#xff0c;程序需要生成一个新的 i…

Linux学习第32天:Linux INPUT 子系统实验(一):接纳

Linux版本号4.1.15 芯片I.MX6ULL 大叔学Linux 品人间百味 思文短情长 题目中用了“接纳”俩字。其实学习就是一个接纳的过程。接纳新的知识&#xff0c;从而转化为自己知识宝库的一部分。那今天学习的input子系统和今天的主题接纳有…

基于单片机设计的自动门控制系统

一、项目介绍 随着科技的不断发展&#xff0c;自动门成为公共场所、商业建筑和住宅社区等地的常见设施。自动门的出现使得进出门的操作更加便捷&#xff0c;提高了人们的生活质量和工作效率。为了实现自动门的开关控制&#xff0c;本项目基于单片机设计了一套自动门控制系统。…

分布式服务框架设计

目录 服务框架的设计 服务框架的功能 服务框架的性能指标 服务治理需要哪些功能 服务框架的设计 尽管不同的分布式服务框架实现细节存在差异&#xff0c;但是核心功能差异不大&#xff0c;下面的架构图描绘了一个分布式服务框架的整体逻辑架构 总共分为 3 层&#xff1a;1…

GNU ld链接器 lang_process()(二)

一、ldemul_create_output_section_statements() 位于lang_process()中11行 。 该函数用于创建与目标有关的输出段的语句。这些语句将用于描述输出段的属性和分配。 void ldemul_create_output_section_statements (void) {if (ld_emulation->create_output_section_sta…

MySQL数据库之表的增删查改

目录 表的操作1.创建表创建表案例 2.查看表结构3.修改表4.删除表 表的操作 1.创建表 语法&#xff1a; CREATE TABLE table_name (field1 datatype,field2 datatype,field3 datatype ) character set 字符集 collate 校验规则 engine 存储引擎;说明&#xff1a; field 表示列…

C# 基类中的虚函数调用基类的虚函数执行的是派生类实现的对应函数吗

答案 &#xff1a; 是的。 比如基类Base中有两个virtual 函数A和B&#xff0c;然后派生类为Derive&#xff0c;override了函数A记为A&#xff0c;override了函数B记为B&#xff0c;且B之中会执行base.B的逻辑&#xff1b; 在Base中&#xff0c;B调用了A的逻辑&#xff0c;那么外…

C++ 实现红黑树

红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制&#xff0c;红黑树确保没有一条路 径会比其他路径长出俩倍&#xff0c;因…

通过环境变量实现多个JDK切换

前文: 由于jdk版本需要升级为jdk17,因为jdk8比较常用且稳定,本人又不想卸载掉安装的jdk8,在经过查找资料后找到了可以通过修改环境变量在本地任意切换jdk版本 环境变量配置 网上教程一堆,直接跳过了,这里主要说明怎么通过配置环境变量切换 电脑->属性->高级系统设置-&g…

centos7中多版本go安装

安装go的方式 官网下载tar.gz包安装 # 1.下载tar包 wget https://go.dev/dl/go1.18.1.linux-amd64.tar.gz # 2.解压tar包到指定路径 tar -xvf go1.18.1.linux-amd64.tar.gz -C /usr/local/go1.18 # 3.配置环境变量&#xff0c;打开 /etc/profile 文件添加以下文件每次开机时…

【MATLAB源码-第65期】基于matlab的OFDM/OTFS通信系统性能对比,输处误码率曲线;对比是否采用LDPC编码。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 OTFS&#xff08;Orthogonal Time Frequency Space&#xff09;是一种无线通信调制技术&#xff0c;它利用时间、频率和空间的正交性来传输数据&#xff0c;目的是提高无线通信系统的性能&#xff0c;尤其是在多径和高移动性环…