力扣—不同路径(路径问题的动态规划)

文章目录

    • 题目解析
    • 算法原理
    • 代码实现
    • 题目练习

题目解析

在这里插入图片描述

算法原理

  1. 状态表示
    对于这种「路径类」的问题,我们的状态表示⼀般有两种形式:
    i. 从[i, j] 位置出发。
    ii. 从起始位置出发,到[i, j] 位置。
    这⾥选择第⼆种定义状态表⽰的⽅式:
    dp[i][j] 表示:⾛到[i, j] 位置处,⼀共有多少种⽅式。
  2. 状态转移⽅程:
    简单分析⼀下。如果dp[i][j] 表示到达[i, j] 位置的⽅法数,那么到达[i, j] 位置之
    前的⼀小步,有两种情况:
    i. 从[i, j] 位置的上方( [i - 1, j] 的位置)向下走⼀步,转移到[i, j] 位置;
    ii. 从[i, j] 位置的左方( [i, j - 1] 的位置)向右走⼀步,转移到[i, j] 位置。
    由于我们要求的是有多少种⽅法,因此状态转移⽅程就呼之欲出了:
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 。
  3. 初始化:
    可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
    i. 辅助结点⾥⾯的值要「保证后续填表是正确的」;
    ii. 「下标的映射关系」。
    在本题中,「添加⼀⾏」,并且「添加⼀列」后,只需将dp[0][1] 的位置初始化为1 即可。
  4. 填表顺序:
    根据「状态转移⽅程」的推导来看,填表的顺序就是「从上往下」填每⼀⾏,在填写每⼀⾏的时候「从左往右」。
  5. 返回值:
    根据「状态表示」,我们要返回dp[m][n] 的值。

代码实现

class Solution {public int uniquePaths(int m, int n) {int[][] dp=new int[m+1][n+1];//dp数组加一行和加一列是防止dp[i-1]越界访问dp[0][1]=1;//因为数组的一行和第一列的元素必须要等于1,为什么是1,因为机器人只能//向右或者向下移动走第一行和第一列的时候只有一种方式,所以是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][n];}
}

题目练习

不同路径||

class Solution 
{public int uniquePathsWithObstacles(int[][] ob) {int m = ob.length, n = ob[0].length;int[][] dp = new int[m + 1][n + 1];dp[1][0] = 1;//第一行第一列设置为1,因为第一行和第一列都只能左移或者向下移动,只有一种方式,所以设置为1for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)if(ob[i - 1][j - 1] == 0)//因为数组初始化为int[m + 1][n + 1];原来的[0][0]下标变为了[1][1]下标,//下标的映射关系发生了改变dp[i][j] = dp[i - 1][j] + dp[i][j - 1];return dp[m][n];}
}

珠宝的的最大价值
下降路径最小和
最小路径和
完。

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

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

相关文章

用了Stream后,代码反而越写越丑?

使用 Stream API 可以使代码更加简洁和易读&#xff0c;但如果不恰当地使用或过度使用&#xff0c;确实可能导致代码变得复杂和难以理解。以下是一些常见的问题和改进建议&#xff1a; 常见问题 过度链式调用&#xff1a;过度链式调用 Stream 方法会导致代码行过长&#xff0c…

论文速读:简化目标检测的无源域适应-有效的自我训练策略和性能洞察(ECCV2024)

中文标题&#xff1a;简化目标检测的无源域适应&#xff1a;有效的自我训练策略和性能洞察 原文标题&#xff1a;Simplifying Source-Free Domain Adaptation for Object Detection: Effective Self-Training Strategies and Performance Insights 此篇文章为论文速读&#xff…

FFmpeg 4.3 音视频-多路H265监控录放C++开发十. 多线程控制帧率。循环播放,QT connect 细节,

在前面&#xff0c;我们总结一下前面的代码。 在 FactoryModeForAVFrameShowSDL 构造函数中 init SDL。 通过 QT timerevent机制&#xff0c;通过startTimer(10);每隔10ms&#xff0c;就会调用timerEvent事件。 在timerEvent事件中&#xff0c;真正的去 读取数据&#xff0c…

企业文件加密要怎么做?好用的10款企业文件加密软件排行榜!

在现代信息化的工作环境中&#xff0c;企业数据安全面临着越来越多的威胁。尤其是当涉及到敏感文件和商业机密时&#xff0c;如何保护这些数据不被泄露或遭受恶意攻击显得尤为重要。企业文件加密成为了保护企业信息安全的关键手段。本文将探讨如何进行企业文件加密&#xff0c;…

20241107给野火LubanCat1-BTB刷Ubuntu的预编译固件并点亮USB接口的热像仪AT600

20241107给野火LubanCat1-BTB刷Ubuntu的预编译固件并点亮USB接口的热像仪AT600 2024/11/7 20:08 缘起&#xff1a;需要使用RK3566的linux/Buildroot系统。 将 鲁班猫的 云盘资料下载之后&#xff0c;发现里面没有Buildroot的预编译固件。 火速联系 淘宝客服&#xff01;转技术支…

VMware没有卸载干净,安装后ping不通

目录 1.问题 2.问题分析 3. 解决办法 &#x1f353; STEP1&#xff1a;卸载VMware &#x1f348; STEP2&#xff1a;services.msc设置 &#x1f352;STEP3&#xff1a;安装everything删除所有与vmware相关的文件 &#x1f351;STEP4&#xff1a;使用CCleaner清理修复注册…

【科普】简述机器学习和深度学习及其相关的算法

文章目录 机器学习1. 基本概念2. 机器学习的分类3. 机器学习的常用方法4. 应用领域5. 挑战与未来6. 未来趋势 机器学习算法 深度学习1.深度学习的基本概念2.深度学习的主要架构3.深度学习的应用4.深度学习的挑战 深度学习算法 机器学习 机器学习是人工智能的一个重要分支&…

HCIP--3实验- 链路聚合,VLAN间通讯,Super VLAN,MSTP,VRRPip配置,静态路由,环回,缺省,空接口,NAT

学习目标&#xff1a; 链路聚合VLAN间通讯Super VLANMSTPVRRPip配置,静态路由,环回&#xff0c;缺省&#xff0c;空接口NAT 学习内容&#xff1a; 实验拓扑实验需求实验需求分析实验配置内容 &#xff08;每一个设备的每一步操作&#xff09;实验结果验证 1.实验拓扑 搭建 …

Zabbix监控架构

目录 1. Zabbix监控架构-CS架构 2. Zabbix极速上手指南 主机规划 2.1 部署ngxphp环境并测试 检查安装结果 2.2 部署数据库 2.3 编译安装zabbix-server服务端及后续配置 2.4 部署前端代码代码进行访问 前端的配置文件(连接数据库与主机名等信息) 2.5 欢迎来到zabbix 2…

【CentOS】中的Firewalld:全面介绍与实战应用(上)

&#x1f407;明明跟你说过&#xff1a;个人主页 &#x1f3c5;个人专栏&#xff1a;《Linux &#xff1a;从菜鸟到飞鸟的逆袭》&#x1f3c5; &#x1f516;行路有良友&#xff0c;便是天堂&#x1f516; 目录 一、引言 1、iptables 时代 2、firewalld 时代 3、 从 ipt…

人工智能未来前景好不好?

人工智能&#xff08;AI&#xff09;正以前所未有的速度改变着我们的世界。随着技术的不断进步&#xff0c;AI不仅在各行各业中扮演着越来越重要的角色&#xff0c;也为求职者和职业发展带来了广阔的机会。那么&#xff0c;人工智能未来的前景如何&#xff1f; 1 高增长行业 人…

湘潭大学软件工程专业选修 SOA 期末考试复习(二)

文章目录 回顾序言第一章课后题填空选择简答 第二章课后题填空选择编程 计划第三章课后题填空选择简答编程 第四章课后题填空选择简答编程 第五章课后题填空选择简答编程 第六章课后题说明 第七章课后题填空选择简答编程 第八章课后题填空选择简答编程 第九章课后题填空选择简答…

JVM垃圾回收详解

前言 当需要排查各种内存溢出问题、当垃圾收集成为系统达到更高并发的瓶颈时&#xff0c;我们就需要对这些“自动化”的技术实施必要的监控和调节。 堆空间的基本结构 Java 的自动内存管理主要是针对对象内存的回收和对象内存的分配。同时&#xff0c;Java 自动内存管理最核…

Hive 操作基础(进阶篇✌️)

Hive 进阶操作 分区表 创建分区表 create table score_part(字段名 字段类型,字段名 字段类型 )partitioned by (分区字段 分区类型) row format delimited fields terminated by \t; 创建单极分区表 注意: 分区的列名不能和数据列名相同.分区列会当做虚拟列出现在数据列…

【Kafka】Windows+KRaft部署指南

【Kafka】WindowsKRaft部署指南 摘要本地环境说明官网快速开始修改config/kraft/server.properties初始化数据存储目录启动 测试创建topic创建生产者创建消费者 FAQ输入行太长。命令语法不正确。问题描述解决方案 参考资料 摘要 Kafka是一种高吞吐量的分布式发布订阅消息系统&…

Docker-软件容器平台

一、容器 1、什么是容器 容器就是将软件打包成标准化单元&#xff0c;以用于开发、交付和部署 容器镜像是轻量的、可执行的独立软件包 &#xff0c;包含软件运行所需的所有内容&#xff1a;代码、运行时环境、系统工具、系统库和设置。容器化软件适用于基于 Linux 和 Windows…

OSS和FastDFS的区别

FastDFS&#xff1a; FastDFS 是一种开源的轻量级分布式文件系统&#xff0c;基于HTTP协议实现。具有高扩展性、高可用性和高稳定性。它解决了大容量文件存储和高效访问的问题&#xff0c;适合作为大容量文件的存储服务器。FastDFS 通过文件系统集群&#xff0c;使得用户可以将…

分离编译(介绍,解决“类模板定义和声明不在同一文件导致链接错误“的问题),类模板实例化原理,

目录 分离编译 介绍 问题代码示例 代码 说明 预处理 编译 链接 类模板实例化原理 总结 解决方法 显式实例化 模板的声明和定义放在一个头文件 分离编译 介绍 分离编译是一种编程技术 允许将程序代码分割成多个文件&#xff0c;每个文件可以独立地编译成目标文件…

云计算答案

情境一习题练习 一、选择题 1、在虚拟机VMware软件中实现联网过程&#xff0c;图中箭头所指的网络连接方式与下列哪个相关&#xff08; C &#xff09;。 A.仅主机模式 B.桥接 C.NAT D.嫁接 2、请问下图这个虚拟化架构属于什么类型&#xff08; A …

如何做好多项目进度管理

在同时管理多个项目时&#xff0c;重要的是要确保每个项目都能按时、按质完成。有效的时间管理、资源优化配置、持续的沟通和使用专业工具是关键要素。这些元素有助于维护项目的整体质量和效率&#xff0c;确保所有项目成员的责任和期望都明确无误。本文将深入探讨如何通过实践…