动态规划Dynamic Programming

在这里插入图片描述

 上篇文章我们简单入门了动态规划(一般都是简单的上楼梯,分析数据等问题)点我跳转,今天给大家带来的是路径问题,相对于上一篇在一维中摸爬滚打,这次就要上升到二维解决问题,但都用的是动态规划思想嘛,所以大差不差,且听我慢慢道来。
还是用一样的方法,用同样的分析思路和技巧来分析问题解决问题。
路径规划
不同路径
在这里插入图片描述

  • 状态表示
     这道题我们需要知道的是从左上角位置走到右下角位置总共有多少的路径,我们可以将问题拆分,题目中所说,机器人每次只能向下或者向右移动一步,所以我们到达右下角位置是怎么到达的呢?
    如图
    在这里插入图片描述所以到达目标的方法就是到达这两个位置方法的总和。
    在这里插入图片描述
    因此这道题的状态表示就是到达ij位置总共的方法数。
  • 状态转移方程
    有了上边的分析,我们可以很清晰地知道
    状态转移方程为

dp[i][j]=dp[i-1][j]+dp[i][j-1]

  • 初始化
     初始化顺序即填表顺序是从左上角到右下角,但是我们应该怎么初始化呢?如果套用我们的状态转移方程,我们会发现在数租的边缘部分一定会遇到越界的情况。
    在这里插入图片描述
     所以在初始化时,我们可以将数组多开一行一列,这样就可以解决越界访问的问题,如何初始化这个表格呢?我们来试着分析。
    在这里插入图片描述
    其他位置全部初始化为0,这样就可以避免多开的数组影响我们后续的得到的结果。
  • 填表顺序
    填表顺序就是从左上角向左下角进行填写。
  • 返回值
    很简单,就是返回填表后到达i,j位置时的值即可
    接下来我们就可以根据分析出的结论写代码了。

class Solution {
public:int uniquePaths(int m, int n) {//new出一个二维数组,并将他们的值初始化为0vector<vector<int>> dp(m+1,vector<int>(n+1));//这里应该怎么给空间啊dp[0][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];}
};

在这里插入图片描述
这里还有一道十分相仿的题目,多了一步扩展的思维而已,尝试一下吧!
不同路径2


第二道题
珠宝的最高价值

在这里插入图片描述
 如果说上一道题对标的是上一篇中的上楼梯的方法数,那么这道题对标的就是上楼梯最小花费。
思路和上一道题目很像,一起来看一看。

  • 状态表示
     同样要创建一个二维数组,到达ij位置可以拿到的珠宝价值最高,那么状态表示就是到达ij位置能拿到的最大珠宝价值,说白了就是所以路径中求和最大的一条路径。
  • 状态转移方程
     移动方式和上一道题目一样,但是相比于上一道题目的相加,这道题目就是从上边或者左边到达ij位置时,他们两个谁的路径和最大。因为上一道题目已经解释很清楚了,这里就不再画图赘述。

dp[i][j]=max(dp[i-1][j],dp[i][j-1];

  • 填表顺序
     从左上角向右下角。要注意是从下表为1,1位置开始填表的。
  • 初始化
     初始化方式和前边那道题目大同小异,只不过我们多开的数组默认为0不用管就行,因为第一个位置只需要加上他这个位置的财宝价值即可。
  • 返回值
    返回到达左下角位置能达到的最高价值数。
    我们还是直接来展示代码吧,毕竟和前边那道题很像,除了状态转移方程不同。
    代码如下
class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {int m=frame.size();int n=frame[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)dp[i][j]=max(dp[i][j-1],dp[i-1][j])+frame[i-1][j-1];return dp[m][n];}
};

在这里插入图片描述
第三道题
下降路径最小和
在这里插入图片描述
 首先来进行题目解析,这道题目只需要从上到下找到最小的路径即可,而且在某位置可以向下边三个位置进行跳转。

  • 状态表示
     状态表示就是到达ij位置时,需要的最小路径和,然后找出最后一行中最小的,就找到了最小路径下降和。
  • 状态转移方程
    可以来画图分析一下
    在这里插入图片描述
     根据我们的状态表示,我们需要找到最小路径和,只需要找到这个位置上边三种情况的最小路径和即可。
    在这里插入图片描述
    当然,到达ij位置时,还需要加上ij位置上的值。
    故而状态转移方程为

dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j+1],dp[i-1][j]))+matrix[i-1][j-1];//要注意这里位置的对应

这里状态对应的问题后边会解释到。

  • 初始化
    这里初始化是一个问题,问题在于在我们求第一行时,第一行的上边并没有数据,访问dp[-1][-1]势必会造成越界访问,如何解决呢?有了上边题目的铺垫,只需要扩展数组即可。
    相信大家已经看到了上边的画图中分别用两种颜色标记,如何初始化才能不影响后续的结果呢?
    在这里插入图片描述
     因为这道题目的数组开的并不规则,所以对应位置容易混淆,如果你匆匆写代码的话,势必会出现这样的问题,
    在这里插入图片描述
    还会出现这样的问题
    在这里插入图片描述
     第一种就是没有空控制好dp表的填写,导致初始化时的INT_MAX参与了运算,第二种就是因为多开两列,多开一行导致的位置判断不准确,以至于越界访问了。

  • 填表顺序
    很明显,从上往下进行填表

  • 返回值
     这里返回值和之前不太一样,需要找到最后一行元素中最小的一个,然后返回即可。
     代码如下,一定要尝试自己写一下,这道题是正方形表格,但是我作为长方形表格来做了,大家可以忽略这些小细节哈。

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int m=matrix.size();int n=matrix[0].size();vector<vector<int>> dp(m+1,vector<int> (n+2,INT_MAX));//怎么把两边初始化为int_max;//cout<<int_max;for(int k=0;k<=n+1;k++){dp[0][k]=0;}for(int i=1;i<=m;i++){for(int j=1;j<=n+1;j++)//这里要注意,只需要初始化我们需要的部分{dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j+1],dp[i-1][j]))+matrix[i-1][j-1];//要注意这里位置的对应}}//此时只需找到最后一行的最小值。int ret=INT_MAX;for(int j=1;j<=n;j++){ret=min(ret,dp[m][j]);}return ret;}
};

 本文到此结束,感谢大家观看,有问题及时提出,我会积极解决的。

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

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

相关文章

关于项目管理的一些思考

1. 概述 1.1 背景 本文是《项目管理知识体系指南&#xff08;PMBOK指南&#xff09;》的读书笔记&#xff0c;并结合软件开发项目过程的一些经验对项目管理进行总结。 1.2 读完本文你可以获得什么&#xff1f; PMBOK 学习笔记。 关于软件项目管理的一些思考和经验。 2. 什…

【网络基础】VRRP虚拟路由冗余协议介绍与配置

目录 一、VRRP的概述 1.1 VRRP的由来 1.2 作用 1.3 基本结构 1.4 状态机流程 1.5 设备类型 二、 实例演示 一、VRRP的概述 1.1 VRRP的由来 局域网中的用户终端通常采用配置一个默认网关的形式访问外部网络&#xff0c;如果此时默认网关设备发生故障&#xff0c;将中断…

【计算机网络实践】Cisco Packet Tracer局域网组网(FTP服务器通过交换机连接客户端)

本文为应对计算机网络第一次实验所写的预习报告 一、实验准备 一台装有Cisco Packet Tracer的PC机&#xff0c;一个大学生大脑。 二、了解FTP和Cisco Packet Tracer 具体内容可在百度搜索&#xff0c;在物理机上用FileZilla Server实现ftp可参看我前面的文章。Cisco Packet Tr…

Power BI ----SVG(圆环图)

圆环图助力矩阵图 定义度量值放置视觉对象 SVG是什么鬼&#xff0c;在现在的Web世界中越来越凸显这一标准的优势。关于SVG&#xff0c;我们只需要知道一点就好 ---- SVG 意为可缩放矢量图形&#xff08;Scalable Vector Graphics&#xff09;。它是使用 XML 格式定义的图像。 由…

C语言经典算法-8

文章目录 其他经典例题跳转链接41.基数排序法42.循序搜寻法&#xff08;使用卫兵&#xff09;43.二分搜寻法&#xff08;搜寻原则的代表&#xff09;44.插补搜寻法45.费氏搜寻法 其他经典例题跳转链接 C语言经典算法-1 1.汉若塔 2. 费式数列 3. 巴斯卡三角形 4. 三色棋 5. 老鼠…

【每周赠书活动第1期】Python编程 从入门到实践 第3版(图灵出品)

编辑推荐 适读人群 &#xff1a;本书适合对Python感兴趣的所有读者阅读。 编程入门就选蟒蛇书&#xff01; 【经典】Python入门经典&#xff0c;常居Amazon等编程类图书TOP榜 【畅销】热销全球&#xff0c;以12个语种发行&#xff0c;影响超过 250 万读者 【口碑】好评如潮…

Python文件读写操作

文件操作注意点 注意点&#xff1a; 1. for line in file --> 会将偏移量移到末尾 2. buffering1 --> 缓冲区中遇到换行就刷新&#xff0c;即向磁盘中写入 3. 读操作结束后&#xff0c;文本偏移量就会移动到读操作结束位置 """编写一个程序,循环不停的写入…

有哪些强大好用的AI表格数据处理工具或者 AI Excel工具?

在繁忙的工作和生活中&#xff0c;处理大量的表格数据往往令人感到头疼。面对一列列数字、一行行文字&#xff0c;我们需要花费大量的时间和精力去整理、核对。然而&#xff0c;随着科技的飞速发展&#xff0c;人工智能&#xff08;AI&#xff09;技术正逐渐改变这一现状。 如…

Mysql数据库:索引管理

目录 一、索引的概述 1、索引的概念 2、索引的作用 3、索引的副作用 4、创建索引的原则依据 5、索引优化 6、索引的分类 7、数据文件与索引文件 二、管理数据库索引 1、查询索引 2、创建索引 2.1 创建普通索引 2.2 创建唯一索引 2.3 创建主键索引 2.4 创建组合…

《边缘计算:连接未来的智慧之桥》

随着物联网、5G等技术的快速发展&#xff0c;边缘计算作为一种新兴的计算模式&#xff0c;正逐渐引起人们的广泛关注。边缘计算通过将数据处理和存储功能放置在距离数据产生源头更近的位置&#xff0c;实现了更快速、更可靠的数据处理和交换&#xff0c;为各行各业带来了前所未…

【项目设计】基于MVC的负载均衡式的在线OJ

项目代码&#xff08;可直接下载运行&#xff09; 一、项目的相关背景 学习编程的小伙伴&#xff0c;大家对力扣、牛客或其他在线编程的网站一定都不陌生&#xff0c;这些编程网站除了提供了在线编程&#xff0c;还有其他的一些功能。我们这个项目只是做出能够在线编程的功能。…

音视频开发之旅(78)- Docker使用和交互流程

目录 1.Docker是什么 2.DockerFile的使用 3.常用命令 4.Docker和Web服务的交互流程 5.资料 一、Docker是什么 Docker通过轻量级的容器化技术&#xff0c;使得应用程序及其依赖可以打包在一个可移植的容器中运行&#xff0c;确保应用在不同环境下的一致性和效率。 1.1 核心…

Affiliate Stores: 建立营销联盟商店的详细教程- US Domain Center主机

第一步&#xff1a;了解营销联盟商店 营销联盟商店是一种电子商务模式&#xff0c;您可以在其中通过推广其他企业的产品或服务来赚取佣金。您在自己的网站上展示其他企业的产品&#xff0c;并在买家购买时获得佣金。通过 WooCommerce 平台&#xff0c;您可以轻松创建一个营销联…

PHP姓名快速匿名化工具(重组脱敏)

PHP姓名重组工具(脱敏/匿名化工具) 将excel数据姓名列粘贴提交&#xff0c;得到随机姓随机中间字随机尾字的重组姓名 那些年自用瞎搞的代码&#xff0c;今日整理成网页交提交得到结果的交互功能分享。 <?php //PHP姓名重组工具(脱敏/匿名化工具) //将excel数据姓名列粘贴…

第十二届蓝桥杯省赛CC++ 研究生组-路径

记录到每个结点的最短距离&#xff0c;以此为基础计算后续结点最优值 #include<iostream> #include<algorithm> using namespace std; typedef long long ll;ll gcd(int a, int b){if(!b) return a;return gcd(b, a % b); }int main(){ll dp[2022] {0};//dp[i]记…

Vue3 中应该使用 Ref 还是 Reactive?

一、引言 在Vue 3中&#xff0c;构建响应式数据结构是构建用户界面和交互体验的核心部分。而在创建这些响应式数据时&#xff0c;我们有两个主要工具&#xff1a;reactive和ref。选择使用哪一个&#xff0c;实际上取决于你的数据结构和访问需求。 reactive主要用于处理复杂的数…

Matlab|【免费】智能配电网的双时间尺度随机优化调度

目录 1 主要内容 基础模型 2 部分代码 3 部分程序结果 4 下载链接 1 主要内容 该程序为文章《Two-Timescale Stochastic Dispatch of Smart Distribution Grids》的源代码&#xff0c;主要做的是主动配电网的双时间尺度随机优化调度&#xff0c;该模型考虑配电网的高效和安…

【小白入门篇1】GPT到底是怎样练成?

由于具有代表性的OpenAI公司GPT模型并没有开源&#xff0c;所以本章节是参考一些开源和现有课程&#xff08;李宏毅&#xff09;讲解ChatGPT原理。本章没有涉及到很多数学运算&#xff0c;比较适合小白了解GPT到底是怎么练成。GPT的三个英文字母分别代表Generative(生成式)&…

了解交互设计:定义、解析及案例演示!

交互设计作为现代设计领域的一个重要分支&#xff0c;对用户体验和产品的成功至关重要。然而&#xff0c;许多人并不了解交互设计的定义和实践方法。本文将深入分析交互设计的概念和重要性&#xff0c;分享精彩的案例&#xff0c;推荐有用的交互设计工具&#xff0c;帮助您创造…

业务服务:redisson

文章目录 前言一、配置1. 添加依赖2. 配置文件/类3. 注入redission3. 封装工具类 二、应用1. RedisUtils工具类的基本使用 三、队列1. 工具类2. 普通队列3. 有界队列&#xff08;限制数据量&#xff09;4. 延迟队列&#xff08;延迟获取数据&#xff09;5. 优先队列&#xff08…