day39算法训练|动态规划part02

62.不同路径

代码随想录

按照动规五部曲来分析:

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 - 1][j] 表示啥,是从(0, 0)的位置到(i - 1, j)有几条路径,dp[i][j - 1]同理。

那么很自然,dp[i][j] = dp[i - 1][j] + dp[i][j - 1],因为dp[i][j]只有这两个方向过来。

3dp数组的初始化

如何初始化呢,首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条,那么dp[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数组

如图所示:

62.不同路径1

63. 不同路径 II

初始化有区别:当有障碍,之后的初始化都需要设置为0

dp数组如何初始化

在62.不同路径 (opens new window)不同路径中我们给出如下的初始化:

vector<vector<int>> dp(m, vector<int>(n, 0)); // 初始值为0
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

因为从(0, 0)的位置到(i, 0)的路径只有一条,所以dp[i][0]一定为1,dp[0][j]也同理。

但如果(i, 0) 这条边有了障碍之后,障碍之后(包括障碍)都是走不到的位置了,所以障碍之后的dp[i][0]应该还是初始值0。

如图:

63.不同路径II

下标(0, j)的初始化情况同理。

所以本题初始化代码为:

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

注意代码里for循环的终止条件,一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作,dp[0][j]同理

工程能力提升:

直接在循环条件里加上obstacleGrid为0,如果某一个地方为1,直接终止循环,让后面的初始化都为0

        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {dp[i][0] = 1;}for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {dp[0][j] = 1;}
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];//如果在起点或终点出现了障碍,直接返回0if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {return 0;}for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {dp[i][0] = 1;}for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {dp[0][j] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;}}return dp[m - 1][n - 1];}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

TCP对数据的拆分

应用程序的数据一般都比较大&#xff0c;因此TCP会按照网络包的大小对数据进行拆分。 当发送缓冲区中的数据超过MSS的长度&#xff0c;数据会被以MSS长度为单位进行拆分&#xff0c;拆分出来的数据块被放进单独的网路包中。 根据发送缓冲区中的数据拆分情况&#xff0c;当判断…

基于Java SSM框架实现水果销售网站系统项目【项目源码+论文说明】计算机毕业设计

基于java的SSM框架实现水果销售网站系统演示 摘要 21世纪的今天&#xff0c;随着社会的不断发展与进步&#xff0c;人们对于信息科学化的认识&#xff0c;已由低层次向高层次发展&#xff0c;由原来的感性认识向理性认识提高&#xff0c;管理工作的重要性已逐渐被人们所认识&a…

【教学类-06-16】20231213 (按比例抽题+乱序or先加再减后乘)X-Y之间“加法减法乘法+-×混合题”

作品展示&#xff1a; 背景需求&#xff1a; 大三班的“第一高手”对我提供的每一套的题目都只有一种反应&#xff1a; “这个是分合题&#xff0c;太简单了” “乘法&#xff0c;乘法我也会&#xff0c;11的1 22的4 33的9&#xff0c;,44十六……” “都太简单了&#xff0…

基于linux系统的Tomcat+Mysql+Jdk环境搭建(三)centos7 安装Tomcat

Tomcat下载官网&#xff1a; Apache Tomcat - Which Version Do I Want? JDK下载官网&#xff1a; Java Downloads | Oracle 中国 如果不知道Tomcat的哪个版本应该对应哪个版本的JDK可以打开官网&#xff0c;点击Whitch Version 下滑&#xff0c;有低版本的&#xff0c;如…

设计模式(3)--对象结构(3)--组合

1. 意图 将对象组合成树形结构以表示“部分-整体”的层次结构。Composite使得用户对单个对象和组合对象的使用具有一致性。 2. 三种角色 抽象组件(Component)、组合式节点(Composite)、叶节点(Leaf) 3. 优点 3.1 定义了包含基本对象和组合对象的类层次结构。 客户代码中&…

C++相关闲碎记录(14)

1、数值算法 &#xff08;1&#xff09;运算后产生结果accumulate() #include "algostuff.hpp"using namespace std;int main() {vector<int> coll;INSERT_ELEMENTS(coll, 1, 9);PRINT_ELEMENTS(coll);cout << "sum: " << accumulate(…

Spring入门

学习的最大理由是想摆脱平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;迟一天就多一天平庸的困扰。各位小伙伴&#xff0c;如果您&#xff1a; 想系统/深入学习某技术知识点… 一个人摸索学习很难坚持&#xff0c;想组团高效学习… 想写博客但无从下手&#xff0c;急需…

鸿蒙ArkTS Web组件加载空白的问题原因及解决方案

问题症状 初学鸿蒙开发&#xff0c;按照官方文档Web组件文档《使用Web组件加载页面》示例中的代码照抄运行后显示空白&#xff0c;纠结之余多方搜索后扔无解决方法。 运行代码 import web_webview from ohos.web.webviewEntry Component struct Index {controller: web_webv…

docker入门小结

docker是什么&#xff1f;它有什么优势&#xff1f; 快速获取开箱即用的程序 docker使得所有的应用传输就像我们日常通过聊天工具文件传输一样&#xff0c;发送方将程序传输到超级码头而接收方也只需通过超级码头进行获取即可&#xff0c;就像一只鲸鱼拖着货物来回运输一样。…

使用java获取nvidia显卡信息

前言 AI开发通常使用到GPU&#xff0c;但通常使用的是python、c等语言&#xff0c;java用的则非常少。这也导致了java在gpu相关的库比较少。现在的需求是要获取nvidia显卡的使用情况&#xff0c;如剩余显存。这里给出两种较简单的解决方案。 基于nivdia-smi工具 显卡是硬件&a…

AMD 自适应和嵌入式产品技术日

概要 时间&#xff1a;2023年11月28日 地点&#xff1a;北京朝阳新云南皇冠假日酒店 主题内容&#xff1a;AMD自适应和嵌入式产品的更新&#xff0c;跨越 云、边、端的AI解决方案&#xff0c;赋能智能制造的机器视觉与机器人等热门话题。 注&#xff1a;本文重点关注FPGA&a…

【51单片机系列】直流电机使用

本文是关于直流电机使用的相关介绍。 文章目录 一、直流电机介绍二、ULN2003芯片介绍三、在proteus中仿真实现对电机的驱动 51单片机的应用中&#xff0c;电机控制方面的应用也很多。在学习直流电机(PWM)之前&#xff0c;先使用GPIO控制电机的正反转和停止。但不能直接使用GPIO…

textarea 网页文本框在光标处添加内容

在前端研发中我们经常需要使用脚本在文本框中插入内容。如果产品要求不能直接插入开始或者尾部&#xff0c;而是要插入到光标位置&#xff0c;此时我们就需要获取光标/光标选中的位置。 很多时候&#xff0c;我在格式化文本处需要选择选项&#xff0c;将选择的信息输入到光标位…

关于“Python”的核心知识点整理大全25

目录 10.3.4 else 代码块、 10.3.5 处理 FileNotFoundError 异常 alice.py 在这个示例中&#xff0c;try代码块引发FileNotFoundError异常&#xff0c;因此Python找出与该错误匹配的 except代码块&#xff0c;并运行其中的代码。最终的结果是显示一条友好的错误消息&#x…

基于循环神经网络长短时记忆(RNN-LSTM)的大豆土壤水分预测模型的建立

Development of a Soil Moisture Prediction Model Based on Recurrent Neural Network Long Short-Term Memory in Soybean Cultivation 1、介绍2、方法2.1 数据获取2.2.用于预测土壤湿度的 LSTM 模型2.3.土壤水分预测的RNN-LSTM模型的建立条件2.4.预测土壤水分的RNN-LSTM模型…

【ArkTS】Watch装饰器

Watch装饰器&#xff0c;相当于Vue中的监听器 以及 React中使用useEffect监听变量 使用Watch装饰器&#xff0c;可以监听一个数据的变化&#xff0c;并进行后续的响应。 使用方法&#xff1a; Watch(‘回调函数’)&#xff0c;写在State装饰器后&#xff08;其实写在前面也行&a…

LabVIEW开发地铁运行安全监控系统

LabVIEW开发地铁运行安全监控系统 最近昌平线发生的故障事件引起了广泛关注&#xff0c;暴露了现有地铁运行监控系统在应对突发情况方面的不足。为了提高地铁系统的运行安全性&#xff0c;并防止类似事件再次发生&#xff0c;提出了一套全面的地铁运行安全监控系统方案。此方案…

[Verilog] Verilog 基本格式和语法

主页&#xff1a; 元存储博客 全文 3000 字 文章目录 1. 声明格式1.1 模块声明1.2 输入输出声明1.3 内部信号声明1.4 内部逻辑声明1.5 连接声明1.6 数据类型声明1.7 运算符和表达式1.8 控制结构 2. 书写格式2.1 大小写2.2 换行2.3 语句结束符2.4 注释2.5 标识符2.6 关键字 1. 声…

python/c++ Leetcode题解——746. 使用最小花费爬楼梯

目录 方法一&#xff1a;动态规划 复杂度分析 方法一&#xff1a;动态规划 假设数组 cost 的长度为 n&#xff0c;则 n 个阶梯分别对应下标 0 到 n−1&#xff0c;楼层顶部对应下标 n&#xff0c;问题等价于计算达到下标 n 的最小花费。可以通过动态规划求解。 创建长度为 n…

【面试】测试/测开(NIG2)

145. linux打印前row行日志 参考&#xff1a;linux日志打印 前10行日志 head -n 10 xx.log后10行日志 tail -n 10 xx.log tail -10f xx.log使用sed命令 sed -n 9,10p xx.log #打印第9、10行使用awk命令 awk NR10 xx.log #打印第10行 awk NR>7 && NR<10 xx.log …