当前位置: 首页 > news >正文

leetCode 62.不同路径 动态规划 + 空间复杂度优化

62. 不同路径 - 力扣(LeetCode)

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

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

示例 1:

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

示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3:

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

示例 4:

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

>>动态规划

机器人从(0,0)位置出发,到(m-1,n-1)终点

按照动规五部曲分析:

1.确定dp数组(dp table)以及下标的含义

dp[i][j] : 表示 从(0,0)出发,到(i,j)有 dp[i][j]条不同的路径

2.确定递推公式

由于机器人每次只能向下或者向右移动一步。所以想要求出dp[i][j],只能从两个方向推导出来,即

dp[i-1][j] 和 dp[i][j-1],也就是说 dp[i][j] = dp[i-1][j] + dp[i][j-1];

3.dp数组的初始化

dp[i][0]一定都是1,因为从(0,0)的位置到(i,0)的路径只有一条;

dp[0][j]一定也都是1,因为从(0,0)的位置到(0,j)的路径只有一条

初始化代码为:

for(int i = 0,i < m;i++) dp[i][0] = 1;
for(int j = 0;j < n;j++) dp[0][j] = 1;

4.确定遍历顺序

dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导出来,那么从左到右一层一层遍历就可以了。可以保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的

5.举例推导dp数组

class Solution {
public:// 动态规划 时间复杂度:O(m x n) 空间复杂度:O(m x n)int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n,0));for(int i=0;i<m;i++) dp[i][0] = 1;for(int j=0;j<n;j++) dp[0][j] = 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];}
};
  • 时间复杂度:O(m * n)
  • 空间复杂度:O(m * n)

其实用一个一维数组(也可以理解是滚动数组)也可以,只是不利于理解,但可以优化空间,建议先理解了二维,再理解一维

class Solution {
public:// 动态规划 时间复杂度:O(m x n) 空间复杂度:O(n)int uniquePaths(int m,int n) {vector<int> dp(n);for(int j = 0;j < n;j++) dp[j] = 1;for(int i = 1;i < m;i++) {for(int j = 1;j < n;j++) {dp[j] += dp[j-1];}}return dp[n-1];}
};
  • 时间复杂度:O(m * n)
  • 空间复杂度:O(n)

 

来自代码随想录的课堂截图

参考和推荐文章、视频:

 代码随想录 (programmercarl.com)

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

相关文章:

leetCode 62.不同路径 动态规划 + 空间复杂度优化

62. 不同路径 - 力扣&#xff08;LeetCode&#xff09; 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish” &#xf…...

在 .NET 8 Release Candidate 1 中推出 .NET MAUI:质量

作者&#xff1a;David Ortinau 排版&#xff1a;Alan Wang 今天&#xff0c;我们很高兴地宣布 .NET MAUI 在 .NET 8 Release Candidate 1 中已经可用&#xff0c;该版本带有适用于生产应用程序的正式许可证&#xff0c;因此您可以放心地将此版本用于生产环境。我们在 .NET 8 中…...

Spring 学习(八)事务管理

1. 事务 1.1 事务的 ACID 原则 数据库事务&#xff08;transaction&#xff09;是访问并可能操作各种数据项的一个数据库操作序列。事务必须满足 ACID 原则——即原子性&#xff08;Atomicity&#xff09;、一致性&#xff08;Consistency&#xff09;、隔离性&#xff08;Iso…...

CodeTON Round 6 (Div 1 + Div 2, Rated, Prizes!)(A - E)

CodeTON Round 6 (Div. 1 Div. 2, Rated, Prizes!)(A - E) CodeTON Round 6 (Div. 1 Div. 2, Rated, Prizes!) A. MEXanized Array&#xff08;分类讨论&#xff09; 可以发现当 n < k 或者 k > x 1 的时候无法构成 &#xff0c; 其余的时候贪心的用 x 最大化贡献即…...

Spring 源码分析(五)——Spring三级缓存的作用分别是什么?

Spring 的三级缓存是经典面试题&#xff0c;也会看到一些文章讲三级缓存与循环依赖之的关系。那么&#xff0c;三级缓存分别存储的什么呢&#xff1f;他们的作用又分别是什么&#xff1f; 一、一、二级缓存 一级缓存是一个名为 singletonObjects 的 ConcurrentHashMap&#x…...

Django基于类视图实现增删改查

第一步&#xff1a;导入View from django.views import View 第二步&#xff1a;新建这个基类 class CLS_executer(View):db DB_executerdef get(self, request):executer_list list(self.db.objects.all().values())return HttpResponse(json.dumps(executer_list), conte…...

matplotlib绘图实现中文宋体的两种方法(亲测)

方法一&#xff1a;这种方法我没有测试。 第一步 找宋体字体 &#xff08;win11系统&#xff09; 2.matplotlib字体目录&#xff0c;如果不知道的话&#xff0c;可以通过以下代码查询&#xff1a; matplotlib.matplotlib_fname() 如果你是Anaconda3 安装的matplotlib&#x…...

非常有用的JavaScript高阶面试技巧!

&#x1f340;一、闭包 闭包是指函数中定义的函数&#xff0c;它可以访问外部函数的变量。闭包可以用来创建私有变量和方法&#xff0c;从而保护代码不受外界干扰。 // 例1 function outerFunction() {const privateVariable "私有变量";function innerFunction()…...

windows 安装Linux子系统 Ubuntu 并配置python3

环境说明&#xff1a; Windows 11 Ubuntu 20.04.6 安装步骤以及问题&#xff1a; 1、开启Windows Subsystem for Linux dism.exe /online /enable-feature /featurename:Microsoft-Windows-Subsystem-Linux /all /norestart 2、开启虚拟机特性 dism.exe /online /enabl…...

pytorch的pixel_shuffle转tflite文件

torch.pixel_shuffle()是pytorch里面上采样比较常用的方法&#xff0c;但是和tensoflow的depth_to_space不是完全一样的&#xff0c;虽然看起来功能很像&#xff0c;但是细微是有差异的 def tf_pixelshuffle(input, upscale_factor):temp []depth upscale_factor *upscale_f…...

sentinel-dashboard-1.8.0.jar开机自启动脚本

启动阿里巴巴的流控组件控制面板需要运行一个jar包&#xff0c;通常需要运行如下命令&#xff1a; java -server -Xms4G -Xmx4G -Dserver.port8080 -Dcsp.sentinel.dashboard.server127.0.0.1:8080 -Dproject.namesentinel-dashboard -jar sentinel-dashboard-1.8.0.jar &…...

c++堆排序-建堆-插入-删除-排序

本文以大根堆为例&#xff0c;用数组实现&#xff0c;它的nums[0]是数组最大值。 时间复杂度分析&#xff1a; 建堆o(n) 插入删除o(logn) 堆排序O(nlogn) 首先上代码 #include<bits/stdc.h>using namespace std; void down(vector<int>&nums, int idx, i…...

使用代理后pip install 出现ssl错误

window直接设置代理 httphttp://127.0.0.1:7890;httpshttp://127.0.0.1...

护眼灯什么价位的好?最具性价比的护眼台灯推荐

到了晚上光线比较弱&#xff0c;这时候就需要开灯&#xff0c;要是孩子需要近距离看字学习等等&#xff0c;给孩子选择的灯具要特别的重视。护眼灯就是目前颇受学生家长青睐的灯具之一&#xff0c;越来越多的人会购买一个护眼灯给自己的孩子让孩子能够在灯光下学习的时候&#…...

vue event bus 事件总线

vue event bus 事件总线 创建 工程&#xff1a; H:\java_work\java_springboot\vue_study ctrl按住不放 右键 悬着 powershell H:\java_work\java_springboot\js_study\Vue2_3入门到实战-配套资料\01-随堂代码素材\day04\准备代码\08-事件总线-扩展 vue --version vue crea…...

深信服云桌面用户忘记密码后的处理

深信服云桌面用户忘记了密码&#xff0c;分两种情况&#xff0c;一个是忘记了登录深信服云桌面的密码&#xff0c;另外一个是忘记了进入操作系统的密码。 一、忘记了登录深信服云桌面的密码 登录虚拟桌面接入管理系统界面&#xff0c;在用户管理中选择用户后&#xff0c;点击后…...

Cocos Creator3.8 实战问题(一)cocos creator prefab 无法显示内容

问题描述&#xff1a; cocos creator prefab 无法显示内容&#xff0c; 或者只显示一部分内容。 creator编辑器中能看见&#xff1a; 预览时&#xff0c;看不见内容&#xff1a; **问题原因&#xff1a;** prefab node 所在的layer&#xff0c;默认是default。 解决方法&…...

朴素贝叶斯深度解码:从原理到深度学习应用

目录 一、简介贝叶斯定理的历史和重要性定义例子 朴素贝叶斯分类器的应用场景定义例子常见应用场景 二、贝叶斯定理基础条件概率定义例子 贝叶斯公式定义例子 三、朴素贝叶斯算法原理基本构成定义例子 分类过程定义例子 不同变体定义例子 四、朴素贝叶斯的种类高斯朴素贝叶斯&a…...

RUST 每日一省:闭包

Rust中的闭包是一种可以存入外层函数中变量或作为参数传递给其他函数的匿名函数。你可以在一个地方创建闭包&#xff0c;然后在不同的上下文环境中调用该闭包来完成运算。和一般的函数不同&#xff0c;闭包可以从定义它的作用域中捕获值。 语法 闭包由“||”和“{}”组合而成。…...

Ubuntu下文件的解压缩操作:常用zip和unzip

Ubuntu下文件的解\压缩 压缩一个文件夹为zip包&#xff0c;加参数-r&#xff1a; zip -r MyWeb.zip MyWeb需要排除目录里某个文件夹&#xff1f;例如我要去掉node_modules&#xff0c;以显著减小压缩包体积&#xff0c;此时该怎么做&#xff1f; zip -r MyWeb.zip ./MyWeb…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

【QT控件】显示类控件

目录 一、Label 二、LCD Number 三、ProgressBar 四、Calendar Widget QT专栏&#xff1a;QT_uyeonashi的博客-CSDN博客 一、Label QLabel 可以用来显示文本和图片. 核心属性如下 代码示例: 显示不同格式的文本 1) 在界面上创建三个 QLabel 尺寸放大一些. objectName 分别…...