力扣 T62 不同路径

题目

连接

思路

思路1 : BFS爆搜

class Solution {
public:
    queue<pair<int,int>>q;
    int uniquePaths(int m, int n) {
        q.push({1,1});  // 起始位置
        vector<pair<int, int>> actions;
        actions.push_back({0, 1});  // 向下
        actions.push_back({1, 0});   // 向右
        int ans = 0;
        while(!q.empty()){
            auto s = q.front();
            q.pop();
            for(auto action : actions){
                int x = s.first, y = s.second;
                if(x == n && y == m) {ans ++; break;}
                x += action.first, y += action.second;
                if(x <= n && y <= m) q.push({x, y});
            }
        }
        return ans;
    }
};

超时了。
在这里插入图片描述

思路2: dp

我们将起始点编号为 { 1 , 1 } \{1,1\} {1,1}
设finish点为: { 2 , 3 } \{2, 3\} {2,3}
d p [ i ] [ j ] dp[i][j] dp[i][j] :到达点 i i i j j j 的最多路径。
转移式子如下:
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][j] = dp[i - 1][j] + dp[i][j - 1] dp[i][j]=dp[i1][j]+dp[i][j1]
d p [ 1 ] [ j ] dp[1][j] dp[1][j] d p [ i ] [ 1 ] dp[i][1] dp[i][1] 均为1.

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[105][105];
        for(int i = 0; i <= m; i++) for (int j = 0; j <= n;j++) dp[i][j] = 1;
        for(int i = 2; i <= m; i++){
            for(int j = 2; j <= n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};

复杂度优化

我们可以优化空间复杂度。原本空间复杂度是 O ( m n ) O(mn) O(mn)的。
我们观察, d p [ i ] [ j ] dp[i][j] dp[i][j]是由 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j] d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j1] 转移过来的。
我们画图:
在这里插入图片描述

红色是目前准备更新的值,其只与绿色和蓝色的值有关。
我们尝试利用 背包思想 把他们进行压缩:
我们把他们压缩成一维,数组中每个值的含义与我们枚举 j j j 的顺序有关:
在这里插入图片描述

我们观察上图,可以发现,需要从左向右枚举 j j j

代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[105];
        for(int i = 0 ; i < 105; i++) dp[i] = 1;
        for(int i = 2; i <= m; i++){
            for(int j = 2; j <= n; j++){
                dp[j] += dp[j - 1];
            }
        }
        return dp[n];
    }
};

注意
dp数组压缩成1维后, d p [ j ] dp[j] dp[j] 的含义仍然是走到 j j j 列,共多少种走法。
因此 d p dp dp数组初始化为1,因为 d p [ 1 ] = 1 dp[1] = 1 dp[1]=1,走到第 1 1 1 列 就一种走法。
最终输出 d p [ n ] dp[n] dp[n]
在这里插入图片描述

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

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

相关文章

论文中eps格式图片制作

在提交论文终稿时&#xff0c;有时需要提交论文中图片的eps格式&#xff0c;这里记录一下eps格式图片制作的过程&#xff0c;方便以后查阅。 论文中eps格式图片制作 PPT绘制的图片转换为eps格式使用代码生成的图片Latex中显示的图片大小跟Ai中设定画板的大小不一致 PPT绘制的图…

ABB机械人模型下载

可以下载不同格式的 https://new.abb.com/products/robotics/zh/robots/articulated-robots/irb-6700 step的打开各部件是分开的&#xff0c;没有装配在一起&#xff0c;打开看单个零件时&#xff0c;我们会发现其各零件是有装配的定位关系的。 新建一个装配环境&#xff0c;点…

ctfshow-web入门-命令执行(web53-web55)

目录 1、web53 2、web54 3、web55 1、web53 这里的代码有点不一样&#xff0c;说一下这两种的区别&#xff1a; &#xff08;1&#xff09;直接执行 system($c); system($c);这种方式会直接执行命令 $c 并将命令的输出直接发送到标准输出&#xff08;通常是浏览器&#xff…

基于机器学习和深度学习的NASA涡扇发动机剩余使用寿命预测(C-MAPSS数据集,Python代码,ipynb 文件)

以美国航空航天局提供的航空涡扇发动机退化数据集为研究对象&#xff0c;该数据集包含多台发动机从启动到失效期间多个运行周期的多源传感器时序状态监测数据&#xff0c;它们共同表征了发动机的性能退化情况。为减小计算成本&#xff0c;需要对原始多源传感器监测数据进行数据…

软件测试--Mysql快速入门

文章目录 软件测试-mysql快速入门sql主要划分mysql常用的数据类型sql基本操作常用字段的约束&#xff1a;连接查询mysql内置函数存储过程视图事务索引 软件测试-mysql快速入门 sql主要划分 sql语言主要分为&#xff1a; DQL&#xff1a;数据查询语言&#xff0c;用于对数据进…

SpringBoot中实现一个通用Excel导出功能

SpringBoot中实现一个通用Excel导出功能 文章目录 SpringBoot中实现一个通用Excel导出功能这个导出功能的特色看效果代码解析1、依赖2、Excel 入参(ExcelExportRequest)3、Excel 出参(ExcelExportResponse)4、ExcelExportField5、ExcelExportUtils 工具类6、ExcelHead 头部…

鸿蒙开发接口安全:【@ohos.userIAM.userAuth (用户认证)】

用户认证 说明&#xff1a; 本模块首批接口从API version 6开始支持。后续版本的新增接口&#xff0c;采用上角标单独标记接口的起始版本。 导入模块 import userIAM_userAuth from ohos.userIAM.userAuth;完整示例 // API version 6 import userIAM_userAuth from ohos.use…

AI全栈工程师的新舞台:Coze(扣子)

前言 在当前科技飞速发展的背景下&#xff0c;Coze作为一款引领潮流的AI应用平台&#xff0c;正以破竹之势重塑着我们对于智能应用的认知。Coze不仅仅是一个工具&#xff0c;它是一个集合了前沿AI技术、高效开发环境与创意无限的应用生态于一体的创新平台&#xff0c;旨在让每…

RabbitMQ-工作模式(Topics模式RPC模式Publisher Confirms模式)

文章目录 Topics模式topic代码示例 RPC模式客户端界面回调队列关联ID总结RPC代码示例 Publisher Confirms模式概述在通道上启用发布者确认单独发布消息批量发布消息异步处理发布者确认总结总体代码示例 更多相关内容可查看 Topics模式 在Topics中&#xff0c;发送的消息不能具…

QT 信号和槽 信号关联到信号示例 信号除了可以绑定槽以外,信号还可以绑定信号

信号除了可以关联到槽函数&#xff0c;还可以关联到类型匹配的信号&#xff0c;实现信号的接力触发。上个示例中因为 clicked 信号没有参数&#xff0c;而 SendMsg 信号有参数&#xff0c;所以不方便直接关联。本小节示范一个信号到信号的关联&#xff0c;将按钮的 clicked 信号…

---java 抽象类 和 接口---

抽象类 再面向对对象的语言中&#xff0c;所以的对象都是通过类来描述的&#xff0c;但如果这个类无法准确的描述对象的 话&#xff0c;那么就可以把这个类设置为抽象类。 实例 这里用到abstract修饰&#xff0c;表示这个类或方法是抽象方法 因为会重写motifs里的show方法…

【已解决】FileNotFoundError: [Errno 3] No such file or directory: ‘xxx‘

&#x1f60e; 作者介绍&#xff1a;我是程序员行者孙&#xff0c;一个热爱分享技术的制能工人。计算机本硕&#xff0c;人工制能研究生。公众号&#xff1a;AI Sun&#xff0c;视频号&#xff1a;AI-行者Sun &#x1f388; 本文专栏&#xff1a;本文收录于《AI实战中的各种bug…

游戏服务器工程实践一:百万级同时在线的全区全服游戏

我应该有资格写这篇文章&#xff0c;因为亲手设计过可以支撑百万级同时在线的全区全服类型的游戏服务器架构。 若干年前我在某公司任职时&#xff0c;参与研发过一款休闲类型的游戏&#xff0c;由 penguin 厂独代。研发的时候&#xff0c;p 厂要求我们的游戏服务器要能支撑百万…

如何自我认同?是否需要执着于社会性认同?

一、自我认同与社会性认同 自我认同与社会性认同是两个相关但又有所区别的概念&#xff0c;它们分别反映了个体在内心深处对自身价值的认知&#xff0c;以及外界&#xff08;尤其是社会&#xff09;对个体价值的评价与接纳。 自我认同 自我认同是指个体基于自身的价值观、能…

【C语言】青蛙跳台阶问题 - 递归算法(一种思路,针对三种不同的情况)

文章目录 1. 前言2. 题目和分析2.1 代码实现2.2 反思 (重点) 3.题目二&#xff08;变式&#xff09;3.1 分析3.2 代码实现 4. 题目三&#xff08;变式&#xff09;4.1 分析4.2 代码实现 1. 前言 相信大家看到青蛙跳台阶问题时&#xff0c;第一时间就会想到递归。那你知道为什么…

暴雨推出X705显示器:23.8英寸100Hz IPS屏

IT资讯 6月 7 日消息&#xff0c;日前&#xff0c;暴雨发布了一款 23.8 英寸 IPS 显示器&#xff0c;直屏、支持 100Hz 刷新率。 据官方介绍&#xff0c;X705 显示器分辨率为 19201080&#xff0c;亮度为 300 尼特&#xff08;典型值&#xff09;&#xff0c;对比度 1000:1&…

Junit(Java单元测试)

目录 配置文件 注解 Test 标注测试方法 BeforeAll 和 AfterAll 标注在测试之前和之后执行的方法 BeforeEach 和 AfterEach 标注在每条测试之前和之后执行的方法 TestMethodOrder 和 Order(优先级) 标注测试方法的执行顺序 ParameterizedTest 将测试方法参数化 ValueSou…

【Activiti7系列】基于Spring Security的Activiti7工作流管理系统简介及实现(附源码)(下篇)

作者&#xff1a;后端小肥肠 上篇&#xff1a;【Activiti7系列】基于Spring Security的Activiti7工作流管理系统简介及实现&#xff08;上篇&#xff09;_spring security activiti7-CSDN博客 目录 1.前言 2. 核心代码 2.1. 流程定义模型管理 2.1.1. 新增流程定义模型数据 …

转让北京劳务分包地基基础施工资质条件和流程

地基基础资质转让流程是怎样的?对于企业来说&#xff0c;资质证书不仅是实力的证明&#xff0c;更是获得工程承包的前提。而在有了资质证书后&#xff0c;企业才可以安心的准备工程投标&#xff0c;进而在工程竣工后获得收益。而对于从事地基基础工程施工的企业&#xff0c;需…

10.1 Go Goroutine

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…