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

动态规划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;}
};

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

相关文章:

动态规划Dynamic Programming

上篇文章我们简单入门了动态规划&#xff08;一般都是简单的上楼梯&#xff0c;分析数据等问题&#xff09;点我跳转&#xff0c;今天给大家带来的是路径问题&#xff0c;相对于上一篇在一维中摸爬滚打&#xff0c;这次就要上升到二维解决问题&#xff0c;但都用的是动态规划思…...

详解机器学习概念、算法

目录 前言 一、常见的机器学习算法 二、监督学习和非监督学习 三、常见的机器学习概念解释 四、深度学习与机器学习的区别 基于Python 和 TensorFlow 深度学习框架实现简单的多层感知机&#xff08;MLP&#xff09;神经网络的示例代码&#xff1a; 欢迎三连哦&#xff01; 前言…...

语音转文字——sherpa ncnn语音识别离线部署C++实现

简介 Sherpa是一个中文语音识别的项目&#xff0c;使用了PyTorch 进行语音识别模型的训练&#xff0c;然后训练好的模型导出成 torchscript 格式&#xff0c;以便在 C 环境中进行推理。尽管 PyTorch 在 CPU 和 GPU 上有良好的支持&#xff0c;但它可能对资源的要求较高&#x…...

第1篇:Mysql数据库表结构导出字段到Excel(一个sheet中)

package com.xx.util;import org.apache.poi.ss.usermodel.*; import org.apache.poi.xssf.usermodel.XSSFWorkbook;import java.sql.*; import java.io.*;public class DatabaseToExcel {public static void main(String[] args) throws Exception {// 数据库连接配置String u…...

Request请求参数----中文乱码问题

一: GET POST获取请求参数: 在处理为什么会出现中文乱码的情况之前, 首先我们要直到GET 以及 POST两种获取请求参数的不同 1>POST POST获取请求参数是通过输入流getReader来进行获取的, 通过字符输入流来获取响应的请求参数, 并且在解码的时候, 默认的情况是 ISO_885…...

labelImg安装方法

labelImg安装方法(简单方法) - 知乎 (zhihu.com) 1. lableImg下载 git clone https://github.com/tzutalin/labelImg.git 2. 制作lableImg所需的"condapython"环境(conda需要先安装,最好再设置下下载源) 打开Anaconda Prompt对话框 # 创建环境 conda create -n …...

吴恩达2022机器学习专项课程(一) 3.6 可视化样例

问题预览 1.本节课主要讲的是什么&#xff1f; 2.不同的w和b&#xff0c;如何影响线性回归和等高线图&#xff1f; 3.一般用哪种方式&#xff0c;可以找到最佳的w和b&#xff1f; 解读 1.课程内容 设置不同的w和b&#xff0c;观察模型拟合数据&#xff0c;成本函数J的等高线…...

C#入门及进阶教程|Windows窗体属性及方法

1.Windows窗体 窗体本身是一个对象&#xff0c;对应于System.Windows.Forms名称空间的Form类。它有自己的属性、方法和事件&#xff0c;用于控制窗体的外观和行为。窗体又是各种控件的容器&#xff0c;用于容纳各种窗体控件。如果想生成窗体&#xff0c;必须从Form类派生出自己…...

34-Java传输对象模式 ( Transfer Object Pattern )

Java传输对象模式 实现范例 传输对象模式&#xff08;Transfer Object Pattern&#xff09;用于从客户端向服务器一次性传递带有多个属性的数据传输对象也被称为数值对象&#xff0c;没有任何行为传输对象是一个具有 getter/setter 方法的简单的 POJO 类&#xff0c;它是可序列…...

flutter实现视频播放器,可根据指定视频地址播放、设置声音,进度条拖动,下载等

需要装依赖&#xff1a; gallery_saver: ^2.3.2video_player: ^2.8.3 AndroidManifest.xml <uses-permission android:name"android.permission.INTERNET"/> 实现代码 import dart:async; import dart:io;import package:flutter/material.dart; import pa…...

微服务(基础篇-001-介绍、Eureka)

目录 认识微服务&#xff08;1&#xff09; 服务架构演变&#xff08;1.1&#xff09; 单体架构&#xff08;1.1.1&#xff09; 分布式架构&#xff08;1.1.2&#xff09; 微服务&#xff08;1.1.3&#xff09; 微服务结构 微服务技术对比 企业需求 SpringCloud(1.2) …...

mac 解决随机出现的蓝色框

macbookair为什么打字的时候按空格键会出现蓝色框? - 知乎...

深入理解与使用go之函数与方法--使用

深入理解与使用go之函数与方法–理解与使用 文章目录 引子函数与方法分类函数函数入参普通参数可变参数默认值返回命名不带命名带命名讨论init 函数defer 函数方法值接收指针接收构造函数引子 在 Go 语言中,函数被视为一等公民(First-Class Citizens),这意味着函数可以像其…...

【QT问题】 Qt信号函数如果重名,调用怎么处理

问题描述&#xff1a; 在调用某个类的信号函数的时候&#xff0c;出现信号函数名字相同&#xff0c;参数不同的情况&#xff0c;但是Qt在链接信号槽的时候&#xff0c;又不需要指明信号函数参数&#xff0c;此时就会出现无法分辨的情况。 例如&#xff1a;QComboBox的信号 Q_…...

登山小分队(dfs,模拟)

原题链接&#xff1a; 题目描述 Foxity和他的好友们相约去爬山&#xff0c;但是他们每个人都来到了不同的山脚下。整个山的结构类似一棵 "树"&#xff0c;有很多的观光节点通过一条条山道连接起来。 在图论中&#xff0c;树是一种无向图&#xff0c;其中任意两个顶…...

Luminar Neo:重塑图像编辑新纪元,Mac与Win双平台畅享创意之旅

在数字时代的浪潮中&#xff0c;图像编辑软件已成为摄影师和设计师们不可或缺的创作工具。Luminar Neo&#xff0c;作为一款专为Mac与Windows双平台打造的图像编辑软件&#xff0c;正以其卓越的性能和创新的编辑功能&#xff0c;引领着图像编辑的新潮流。 Luminar Neo不仅继承…...

计算机二级Python题库深度解析与备考策略

计算机二级Python题库深度解析与备考策略 随着信息技术的飞速发展&#xff0c;Python作为一门简洁、易读且功能强大的编程语言&#xff0c;受到了越来越多人的青睐。计算机二级Python考试作为衡量考生Python编程水平的重要标准&#xff0c;其题库内容涵盖了Python语言的基础知…...

微信商家转账到零钱:实用指南,涵盖开通、使用与常见问题

商家转账到零钱是什么&#xff1f; 商家转账到零钱功能整合了企业付款到零钱和批量转账到零钱&#xff0c;支持批量对外转账&#xff0c;操作便捷。如果你的应用场景是单付款&#xff0c;体验感和企业付款到零钱基本没差别。 商家转账到零钱的使用场景有哪些&#xff1f; 这…...

[精选]Kimi到底是什么,将带来什么?

## 阿里通义千问重磅升级&#xff1a;免费开放1000万字长文档处理功能。 Kimi突然的泼天富贵&#xff0c;大家都想沾一把。短期这一块大概率会继续热一段时间。 作为月之暗面的创始人&#xff0c;杨植麟常把他的AGI梦想形容为“登月计划”&#xff0c;长文本就是这个伟大计划…...

MySQL学习笔记------SQL(2)

ziduanSQL DML 全称为&#xff1a;Data Manipulation Language&#xff0c;用来对数据库中表的数据记录进行增删改操作 插入数据 添加数据&#xff08;INSERT&#xff09; 给指定字段添加数据&#xff1a;INSERT INTO 表名(字段名1&#xff0c;字段名2&#xff0c;......…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

Mysql故障排插与环境优化

前置知识点 最上层是一些客户端和连接服务&#xff0c;包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念&#xff0c;为通过安全认证接入的客户端提供线程。同样在该层上可…...

node.js的初步学习

那什么是node.js呢&#xff1f; 和JavaScript又是什么关系呢&#xff1f; node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说&#xff0c; 需要在node.js的环境上进行当JavaScript作为前端开发语言来说&#xff0c;需要在浏览器的环境上进行 Node.js 可…...