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

LeetCode、62.不同路径的数目(一)【简单,动态规划或递归】

文章目录

  • 前言
  • LeetCode、62.不同路径的数目(一)【简单,动态规划或递归】
    • 题目描述与分类
    • 思路
      • 思路1:动态规划
      • 思路2:递归实现
      • 简洁写法补充:2024.1.30
  • 资料获取

前言

博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。

涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。

博主所有博客文件目录索引:博客目录索引(持续更新)

视频平台:b站-Coder长路


LeetCode、62.不同路径的数目(一)【简单,动态规划或递归】

题目描述与分类

牛客:不同路径的数目(一)

leetcode:LeetCode、62.不同路径的数目(一)【简单,动态规划或递归】

题目内容:一个机器人在m×n大小的地图的左上角(起点)。机器人每次可以向下或向右移动。机器人要到达地图的右下角(终点)。

可以有多少种不同的路径从起点走到终点?

思考区

分类:动态规划/线性DP(二维)

约束条件:

1、机器人每次只能往右或者往下走。

2、机器人不能越界。


思路

思路1:动态规划

定义状态方程:

dp[i][j] = val  i表示行,j表示列,val表示方案数量
当i>1 && j>1  dp[i][j] = dp[i][j-1] + dp[i-1][j]
当i=0时,dp[i][j] = dp[i][j-1]
当j=0时,dp[i][j] = dp[i-1][j]

复杂度分析:

  • 时间复杂度:O(n*m)
  • 空间复杂度:O(n*m)

代码:

import java.util.*;public class Solution {/*** * @param m int整型 * @param n int整型 * @return int整型*/public int uniquePaths (int m, int n) {//定义dp数组int[][] dp= new int[m][n];for (int i = 0;i < m; i++) {for (int j = 0; j < n; j++) {if (i == 0) {dp[i][j] = 1;continue;}if (j == 0) {dp[i][j] = 1;continue;}dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
}
class Solution {//线性dp//dp(i, j) = dp(i-1,j) + dp(i,j-1)public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for (int i = 0; i < m; i ++) {for (int j = 0; j < n; j ++) {if (i == 0 || j == 0) dp[i][j] = 1;else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
}

思路2:递归实现

import java.util.*;public class Solution {/*** * @param m int整型 * @param n int整型 * @return int整型*/public int uniquePaths (int m, int n) {if (m == 1 || n == 1) {return 1; }return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);}
}

上面的时间复杂度是2n,如何优化呢?进行记忆化状态方程

class Solution {private int[][] dp;public int uniquePaths(int m, int n) {if (dp == null) {dp = new int[m + 1][n + 1];}if (m == 1 || n == 1) {return 1;}if (dp[m][n] == 0) {dp[m][n] = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);}return dp[m][n];}
}

简洁写法补充:2024.1.30

class Solution {int[][] dp = new int[101][101];//线性dp//dp(i, j) = dp(i-1,j) + dp(i,j-1)public int uniquePaths(int m, int n) {if (m == 1 || n == 1) dp[m][n] = 1;if (dp[m][n] != 0) return dp[m][n];dp[m][n] = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);return dp[m][n];}
}

此时无论是时间还是空间复杂度与思路1一致。


资料获取

大家点赞、收藏、关注、评论啦~

精彩专栏推荐订阅:在下方专栏👇🏻

  • 长路-文章目录汇总(算法、后端Java、前端、运维技术导航):博主所有博客导航索引汇总
  • 开源项目Studio-Vue—校园工作室管理系统(含前后台,SpringBoot+Vue):博主个人独立项目,包含详细部署上线视频,已开源
  • 学习与生活-专栏:可以了解博主的学习历程
  • 算法专栏:算法收录

更多博客与资料可查看👇🏻获取联系方式👇🏻,🍅文末获取开发资源及更多资源博客获取🍅


整理者:长路 整理时间:2024.1.31

相关文章:

LeetCode、62.不同路径的数目(一)【简单,动态规划或递归】

文章目录 前言LeetCode、62.不同路径的数目(一)【简单&#xff0c;动态规划或递归】题目描述与分类思路思路1&#xff1a;动态规划思路2&#xff1a;递归实现简洁写法补充&#xff1a;2024.1.30 资料获取 前言 博主介绍&#xff1a;✌目前全网粉丝2W&#xff0c;csdn博客专家、…...

re:从0开始的CSS学习之路 4. 长度单位

1. 长度单位 像素px&#xff1a;一个像素就是屏幕中一个不可分割的点。我们应用的屏幕实际上是由一个个的像素点构成的。 不同显示器的像素点大小也不同&#xff0c;在屏幕尺寸相同的情况下&#xff0c;像素越小&#xff0c;显示效果越清晰。 大部分浏览器默认字体大小是16px …...

golang开源定时任务调度框架

golang开源定时任务调度框架 Go语言中有很多开源的定时任务调度框架&#xff0c;以下几个是比较流行常用的&#xff1a; golang开源定时任务框架介绍 cron 一个基于Cron表达式的定时任务库&#xff0c;可以精确到秒级。它提供了简单易用的API来定义和管理定时任务&#xff…...

GridModel事件集合——yonBIP低代码

我们接着看表格相关的事件&#xff0c;用友的文档打不开&#xff0c;真的是天大的404&#xff0c;客观请看这个开发文档网址&#xff0c;找不到了&#xff0c;你说holy 不咯&#xff1f;http://tinper.org/mdf/&#xff08;如果有哪位小伙伴知道这个地址是不是迁移了的话&#…...

苹果macbook电脑删除数据恢复该怎么做?Mac电脑误删文件的恢复方法

苹果电脑删除数据恢复该怎么做&#xff1f;Mac电脑误删文件的恢复方法 如何在Mac上恢复误删除的文件&#xff1f;在日常使用Mac电脑时&#xff0c;无论是工作还是娱乐&#xff0c;我们都会创建和处理大量的文件。然而&#xff0c;有时候可能会不小心删除一些重要的文件&#x…...

2024年R2移动式压力容器充装证模拟考试题库及R2移动式压力容器充装理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年R2移动式压力容器充装证模拟考试题库及R2移动式压力容器充装理论考试试题是由安全生产模拟考试一点通提供&#xff0c;R2移动式压力容器充装证模拟考试题库是根据R2移动式压力容器充装最新版教材&#xff0c;R2…...

云开发超多功能工具箱组合微信小程序源码/附带流量主

这是一款云开发超多功能工具箱组合微信小程序源码附带流量主功能&#xff0c;小程序内包含了40余个功能&#xff0c;堪称全能工具箱了&#xff0c;大致功能如下&#xff1a; 证件照制作 | 垃圾分类查询 | 个性签名制作 二维码生成丨文字九宫格 | 手持弹幕丨照片压缩 | 照片编…...

挑战杯 python+深度学习+opencv实现植物识别算法系统

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 基于深度学习的植物识别算法研究与实现 &#x1f947;学长这里给一个题目综合评分(每项满分5分) 难度系数&#xff1a;4分工作量&#xff1a;4分创新点&#xff1a;4分 &#x1f9ff; 更多…...

pytest的常用插件和Allure测试报告

pytest常用插件 pytest-html插件 安装&#xff1a; pip install pytest-html -U 用途&#xff1a; 生成html的测试报告 用法&#xff1a; ​在.ini配置文件里面添加 addopts --htmlreport.html --self-contained-html 效果&#xff1a; 执行结果中存在html测试报告路…...

神经网络的权重是什么?

请参考这个视频https://www.bilibili.com/video/BV18P4y1j7uH/?spm_id_from333.788&vd_source1a3cc412e515de9bdf104d2101ecc26a左边是拟合的函数&#xff0c;右边是均方和误差&#xff0c;也就是把左边的拟合函数隐射到了右边&#xff0c;右边是真实值与预测值之间的均方…...

C语言代码 在屏幕上输出9*9乘法口诀表

在屏幕上输出9*9乘法口诀表。 代码示例&#xff1a; #include <stdio.h>int main() {int i 0;for (i 1; i < 9; i)//打印所有行的循环{int j 0;for (j 1; j < i; j)//打印每一行中所有列的循环{printf("%d*%d%-2d ", i, j, i * j);//%-2d的意思是两…...

11.0 Zookeeper watcher 事件机制原理剖析

zookeeper 的 watcher 机制&#xff0c;可以分为四个过程&#xff1a; 客户端注册 watcher。服务端处理 watcher。服务端触发 watcher 事件。客户端回调 watcher。 其中客户端注册 watcher 有三种方式&#xff0c;调用客户端 API 可以分别通过 getData、exists、getChildren …...

HGAME 2024 WEEK 1 :web ezHTTP

题目&#xff1a; 看到这个就知道是文件头伪造 第一想法就是Referer伪造 所以伪造 Referer: vidar.club 然后构造伪造的Referer 然后提示通过那些东西访问页面&#xff0c;User-Agent: 是构造你浏览器访问信息的&#xff0c;所以复制右边那一串替代就好了 然后要求我们从本地…...

Linux【docker 设置阿里源】

文章目录 一、查看本地docker的镜像配置二、配置阿里镜像三、检查配置 一、查看本地docker的镜像配置 docker info一般没有配置过是不会出现Registry字段的 二、配置阿里镜像 直接执行下面代码即可&#xff0c;安装1.10.0以上版本的Docker客户端都会有/etc/docker 1.建立配置…...

app逆向-frida-rpc详解

Frida-RPC是Frida工具的一个组件&#xff0c;用于在应用程序和Frida脚本之间进行远程过程调用&#xff08;RPC&#xff09;。远程过程调用是一种允许应用程序的不同部分或不同的应用程序之间进行通信的方法。在Frida中&#xff0c;RPC通过JavaScript脚本和应用程序之间建立通信…...

计算机网络(第六版)复习提纲27

7 TCP流量控制 A 利用滑动窗口实现流量控制 所谓流量控制&#xff0c;就是让发送方发送速率不要太快&#xff0c;让接收方来得及接收 1 利用窗口进行流量控制 2 持续计时器和零窗口探测报文&#xff08;仅携带一字节的数据&#xff09; B TCP的传输效率&#xff08;TCP报文段的…...

解析与模拟常用字符串函数strcpy,strcat,strcmp,strstr(一)

今天也是去学习了一波字符串函数&#xff0c;想着也为了加深记忆&#xff0c;所以写一下这篇博客。既帮助了我也帮助了想学习字符串函数的各位。下面就开始今天的字符串函数的学习吧。 目录 strcpy与strncpy strcat与strncat strcmpy strstr strcpy与strncpy 在 C 语言中&…...

node.js后端+小程序前端+mongoDB(增删改查)

前言 今天我对比了以下node.js的express与python的fastAPI&#xff0c;我决定我还是出一期关于node.jsmangoDB小程序的小案例吧。 不是python的fastAPI不好用&#xff0c;因为fastAPI是python较新的技术&#xff0c;我不敢果断发出教学文章&#xff08;这件事情还是留着给pyt…...

thinkphp数据批量提交(群发消息)

<form id="edit-form" class="form-horizontal" role="form" data-toggle<...

大华 DSS 数字监控系统 attachment_getAttList.action SQL 注入漏洞复现

0x01 产品简介 大华 DSS 数字监控系统是大华开发的一款安防视频监控系统,拥有实时监视、云台操作、录像回放、报警处理、设备管理等功能。 0x02 漏洞概述 大华 DSS存在SQL注入漏洞,攻击者 /portal/attachment_getAttList.action 路由发送特殊构造的数据包,利用报错注入获…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...