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

leetcode hot100不同路径

在这里插入图片描述
本题可以采用动态规划来解决。还是按照五部曲来做
确定dp数组:dp[i][j]表示走到(i,j)有多少种路径

确定递推公式:我们这里,只有两个移动方向,比如说我移动到(i,j)那么只能从(i-1,j)或者从(i,j-1)移动,所以,dp[i][j] = dp[i-1][j] + dp[i][j-1]。因为我们求的是路径,并不是步数,所以从dp[i-1][j]到dp[i][j]只有一个路径,同理,所以二者相加即可。

初始化:我们要知道,只能向下或者向右走,也就是说只有两个移动方向,那么如果我们只在第一行移动的时候,dp[0][j]=1,数组的值都是1;同理,只在第一列上移动,dp[i][0]=1;

遍历顺序:我们直接从左到右从上到下依次遍历即可(题中规定)

打印

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

注意:

  1. 初始化的时候,按照上述分析直接初始化即可,第一行或者第一列只有一种路径。
  2. 在初始化的时候,只需要初始化到m-1/n-1,因为我们是从下标0开始的。
  3. 在遍历的时候,我们应该从1开始,因为0已经初始化了(行/列)。我们for循环结束的条件就是i<m/j<n,因为我们最后是要走到(i,j)的路径个数,但数组我们是从0开始的,所以只需要<m就可以,并不需要i<=m,并直接返回dp[m-1][n-1]即可。

相关文章:

leetcode hot100不同路径

本题可以采用动态规划来解决。还是按照五部曲来做 确定dp数组&#xff1a;dp[i][j]表示走到&#xff08;i&#xff0c;j&#xff09;有多少种路径 确定递推公式&#xff1a;我们这里&#xff0c;只有两个移动方向&#xff0c;比如说我移动到&#xff08;i&#xff0c;j&#x…...

【前端工程化面试题目】webpack 的热更新原理

可以在顺便学习一下 vite 的热更新原理&#xff0c;请参考这篇文章。 首先有几个知识点需要明确 热更新是针对开发过程中的开发服务器的&#xff0c;也就是 webpack-dev-serverwebpack 的热更新不需要额外的插件&#xff0c;但是需要在配置文件中 devServer属性中配置&#x…...

不花一分钱,在 Mac 上跑 Windows(M1/M2 版)

这是在 MacOS M1 上体验最新 Windows11 的效果&#xff1a; VMware Fusion&#xff0c;可以运行 Windows、Linux 系统&#xff0c;个人使用 licence 免费 安装流程见 &#x1f449; https://zhuanlan.zhihu.com/p/452412091 从申请 Fusion licence 到下载镜像&#xff0c;再到…...

Attempt to call an undefined function glutInit

Attempt to call an undefined function glutInit 解决方法&#xff1a; 从这里下载PyOpenGL 的whl安装文件&#xff0c; https://drive.google.com/drive/folders/1mz7faVsrp0e6IKCQh8MyZh-BcCqEGPwx 安装命令举栗 pip install PyOpenGL-3.1.7-cp39-cp39-win_amd64.whl pi…...

AB测试最小样本量

1.AB实验过程 常见的AB实验过程&#xff0c;分流-->实验-->数据分析-->决策&#xff1a;分流&#xff1a;用户被随机均匀的分为不同的组实验&#xff1a;同一组内的用户在实验期间使用相同的策略&#xff0c;不同组的用户使用相同或不同的策略。数据收集&#xff1a;…...

在Spring中事务失效的场景

在Spring框架中&#xff0c;事务管理是通过AOP&#xff08;面向切面编程&#xff09;实现的&#xff0c;主要依赖于Transactional注解。然而&#xff0c;在某些情况下&#xff0c;事务可能会失效。以下是一些可能导致Spring事务失效的常见场景&#xff1a; 非public方法&#…...

Rust 学习笔记 - 变量声明与使用

前言 任何一门编程语言几乎都脱离不了&#xff1a;变量、基本类型、函数、注释、循环、条件判断&#xff0c;这是一门编程语言的语法基础&#xff0c;只有当掌握这些基础语法及概念才能更好的学习 Rust。 变量介绍 Rust 是一种强类型语言&#xff0c;但在声明变量时&#xf…...

windows 下跑起大模型(llama)操作笔记

原贴地址&#xff1a;https://testerhome.com/topics/39091 前言 国内访问 chatgpt 太麻烦了&#xff0c;还是本地自己搭一个比较快&#xff0c;也方便后续修改微调啥的。 之前 llama 刚出来的时候在 mac 上试了下&#xff0c;也在 windows 上用 conda 折腾过&#xff0c;环…...

人工智能专题:基础设施行业智能化的基础设施,自智网络双价值分析

今天分享的是人工智能系列深度研究报告&#xff1a;《人工智能专题&#xff1a;基础设施行业智能化的基础设施&#xff0c;自智网络双价值分析》。 &#xff08;报告出品方&#xff1a;埃森哲&#xff09; 报告共计&#xff1a;32页 自智网络驱动的电信产业变革 经过多年的…...

docker 编译安装redis脚本

在Docker中编译安装Redis通常不是一个常见的做法&#xff0c;因为Redis官方提供了预编译的Docker镜像&#xff0c;这些镜像包含了已经编译好的Redis二进制文件。不过&#xff0c;如果你有特殊需求&#xff0c;想要自己从源代码编译Redis并打包成Docker镜像&#xff0c;你可以使…...

鸿蒙开发系列教程(二十三)--List 列表操作(2)

列表样式 1、设置内容间距 在列表项之间添加间距&#xff0c;可以使用space参数&#xff0c;主轴方向 List({ space: 10 }) { … } 2、添加分隔线 分隔线用来将界面元素隔开&#xff0c;使单个元素更加容易识别。 startMargin和endMargin属性分别用于设置分隔线距离列表侧…...

C#根据权重抽取随机数

&#xff08;游戏中一个很常见的简单功能&#xff0c;比如抽卡抽奖抽道具&#xff0c;或者一个怪物有多种攻击动作&#xff0c;按不同的权重随机出个攻击动作等等……&#xff09; 假如有三种物品 A、B、C&#xff0c;对应的权重分别是A&#xff08;50&#xff09;&#xff0c…...

SORA:OpenAI最新文本驱动视频生成大模型技术报告解读

Video generation models as world simulators&#xff1a;作为世界模拟器的视频生成模型 1、概览2、Turning visual data into patches&#xff1a;将视觉数据转换为补丁3、Video compression network&#xff1a;视频压缩网络4、Spacetime Latent Patches&#xff1a;时空潜在…...

阿里云第七代云服务器ECS计算c7、通用g7和内存r7配置如何选择?

阿里云服务器配置怎么选择合适&#xff1f;CPU内存、公网带宽和ECS实例规格怎么选择合适&#xff1f;阿里云服务器网aliyunfuwuqi.com建议根据实际使用场景选择&#xff0c;例如企业网站后台、自建数据库、企业OA、ERP等办公系统、线下IDC直接映射、高性能计算和大游戏并发&…...

视觉slam十四讲学习笔记(六)视觉里程计 1

本文关注基于特征点方式的视觉里程计算法。将介绍什么是特征点&#xff0c;如何提取和匹配特征点&#xff0c;以及如何根据配对的特征点估计相机运动。 目录 前言 一、特征点法 1 特征点 2 ORB 特征 FAST 关键点 BRIEF 描述子 3 特征匹配 二、实践&#xff1a;特征提取…...

PyTorch-线性回归

已经进入大模微调的时代&#xff0c;但是学习pytorch&#xff0c;对后续学习rasa框架有一定帮助吧。 <!-- 给出一系列的点作为线性回归的数据&#xff0c;使用numpy来存储这些点。 --> x_train np.array([[3.3], [4.4], [5.5], [6.71], [6.93], [4.168],[9.779], [6.1…...

C++数据结构与算法——栈与队列

C第二阶段——数据结构和算法&#xff0c;之前学过一点点数据结构&#xff0c;当时是基于Python来学习的&#xff0c;现在基于C查漏补缺&#xff0c;尤其是树的部分。这一部分计划一个月&#xff0c;主要利用代码随想录来学习&#xff0c;刷题使用力扣网站&#xff0c;不定时更…...

掌上新闻随心播控,HarmonyOS SDK助力新浪新闻打造精致易用的资讯服务新体验

原生智能是HarmonyOS NEXT的核心亮点之一&#xff0c;依托HarmonyOS SDK丰富全面的开放能力&#xff0c;开发者只需通过几行代码&#xff0c;即可快速实现AI功能。新浪新闻作为鸿蒙原生应用开发的先行者之一&#xff0c;从有声资讯入手&#xff0c;将基于Speech Kit朗读控件上线…...

2024年危险化学品经营单位主要负责人证模拟考试题库及危险化学品经营单位主要负责人理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年危险化学品经营单位主要负责人证模拟考试题库及危险化学品经营单位主要负责人理论考试试题是由安全生产模拟考试一点通提供&#xff0c;危险化学品经营单位主要负责人证模拟考试题库是根据危险化学品经营单位主…...

C/C++如何把指针所指向的指针设为空指针?

实践出真知&#xff0c;指针对于初学的友友来说&#xff0c;头都要大了。喵喵一直遵循在实践中学&#xff0c;在学习中实践&#xff0c;相信你也会有所得&#xff01; 以下是该问题的解决方案&#xff1a; int** ptrPtr new int*; // 创建指向指针的指针 int* ptr new int;…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...