动态规划训练1

news/2024/6/16 11:24:49/文章来源:https://blog.csdn.net/qq_64484137/article/details/137260672

一、leetcode 91解码方法

1、题目解析

这道题就是需要我们对一个数组进行解码,返回有多少种方法就行了。

但是有几个特殊情况:06 不可以为一组、60 也不可以、6 、0也不行 

2、算法原理

a状态表示

根据经验+题目要求确定表示方程

以i位置为结尾,。。。。或者以i位置开始,。。。。

表示方程:dp[i] 从0开始到i位置的解码方法总数

b状态转移方程

根据最近的一步划分问题

i位置单独解码或者  与i-1合并解码

状态转移方程:dp[i]=dp[i-1]+dp[i-2],成功的情况相加

 

c初始化

dp[1]有两种情况,与dp[0]单独解码或者合并解码

d填表顺序

从左往右

e返回值

dp[n-1]

3、代码

class Solution {
public:int numDecodings(string s) {int n=s.size();vector<int > dp(n);//初始化if('1'<=s[0]&&s[0]<='9')  dp[0]=1;else dp[0]=0;//dp[0]=s[0]!='0';//处理边界情况if(s.size()==1){return dp[0];}if(s[1]!='0') dp[1]+=dp[0];int t=(s[0]-'0')*10+s[1]-'0';if(10<=t&&t<=26)dp[1]+=1;//填表for(int i=2;i<n;i++){if(s[i]!='0')   dp[i]+=dp[i-1];int t=(s[i-1]-'0')*10+s[i]-'0';if(10<=t&&t<=26)dp[i]+=dp[i-2];}return dp[n-1];}
};

o(n)

优化

处理边界问题以及初始化问题技巧

添加一个虚拟节点

虚拟节点如何设值——抱枕后续填表时正确的,就比如新表ndp[2]和ndp[1]可以合并,为了保证期准确度我们给ndp[0]设值为1.

需要注意的映射关系,ndp下标-1才是对一的s下标,

优化后代码:

class Solution
{
public:int numDecodings(string s){// 优化int n = s.size();vector<int> dp(n + 1); dp[0] = 1; // 保证后续填表是正确的dp[1] = s[0] != '0';// 填表for (int i = 2; i <= n; i++){// 处理单独编码if (s[i - 1] != '0') dp[i] += dp[i - 1];// 如果和前⾯的⼀个数联合起来编码int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';if (t >= 10 && t <= 26) dp[i] += dp[i - 2];}return dp[n];}
};

二、62不同路径

1、题目解析

机器人只能向下或者向上移动

2、算法原理

a状态表示

经验+题目要求

以[i][j]为结尾+

b状态转移方程

最近的一步。划分问题

要么从上面要么从左边来

c初始化

与第一题类似,为了避开繁琐的初始化行为,第一题是一维数组添加一个节点即可,

二维数组我们需要初始化的值是第一行和第一列为了避免越界问题。我们可以与第一题类似的方式设置虚拟节点。

为了确保后面的值是正确的,在1,1的上面或者左边设置一个1即可。

c填表顺序

上到下,左到右

d返回值

dp[m][n]

代码

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int >> dp(m+1,vector<int>(n+1,0));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];}
};

vector初始化

三、不同路径2

1、题目解析

2、算法原理

a.状态表示

dp[i][j]表示起始位置到这里有多少种方法

b.状态转移方程

遇到障碍就不相加,将其视作0,让其保持0 的状态,其他位置相加遇到障碍时就相加也不会有影响。

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

c.初始化

1.用虚拟节点的方法,最重要的是让1,1位置赋值为1就行了,能够保证后续填表的正确。

2.这里的映照关系平特别注意一下

e填表顺序

左到右上到下

e代码

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {//创建数组dp//初始化//填表//返回值int m=obstacleGrid.size();int n=obstacleGrid[0].size();vector<vector<int >> dp(m+1,vector<int> (n+1,0));dp[1][0]=1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(obstacleGrid[i-1][j-1]==0)dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}
};

四、47.礼物最大价值

1、题目解析

就是说从左上往右下走最多能拿多贵的礼物

2、算法原理

a状态表示

经验+题目要求

dp[i][j]表示,到这个位置能达到最贵重的礼物

b状态装移方程

根据最近的一步划分问题

观察来时的路,那一条更加贵重一些

c初始化

1.虚拟节点的值需要保证后续填表时的值是正确的

设置为0即可。

(0,1)和(1,0)位置应该设置为0,不影响1,1位置的取值,(0,2)位置应该设置为负无穷,为了不影响1,1到1,2的取值,但是题目要求说明了输入的价格都是大于零的数,所以我们直接取0即可

2.注意下标映射关系

frame中查找价格时需要将下标-1,

d填表顺序

左上到右下

e返回值

dp[m][n]

f代码

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {//建dpint m=frame.size(),n=frame[0].size();vector<vector<int>> dp(m+1,vector<int> (n+1,0));//初始化,为0即可//填表for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];}}//返回值return dp[m][n];}
};

五、下降路径最小和

1、题目解析

2、算法原理

a状态方程

经验+题目要求

dp[i][j]表示。。。

dp[i][j]表示从上到下最小的路径和

b状态转移方程

不好却低呢是哪一条、路线,但是能保证自己这个节点怎么样最小,细分问题

根据距离dp[i][j]最近的值进行问题划分。

dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+m[i][j]

c初始化

1、虚拟节点需要保证后续填表的正确性

第一行设为0,因为要向下相加

第一列最后一列设置为最大值(该值为INT_MAX)

这里非常容易忽视最后一列

2、注意下标映射关系

-1-1

d填表顺序

从左到右,从上到下

e返回值

返回最后一排最小的值

3、代码

class Solution {int my_min(int &a,int &b,int &c){int tem;tem=a<b?a:b;return tem<c?tem:c;}public:int minFallingPathSum(vector<vector<int>>& matrix) {int m=matrix.size();vector<vector<int>> dp(m+1,vector<int>(m+2,INT_MAX));for(int i=0;i<=m;i++){dp[0][i]=0;}//填表for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){dp[i][j]=my_min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+matrix[i-1][j-1];}}int min=INT_MAX;for(int j=1;j<=m;j++){if(dp[m][j]<min)min=dp[m][j];}        return min;}
};

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

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

相关文章

雷军之夜:小米汽车SU7发布会后的智能化探索与网络安全考量

引言 3月28日晚&#xff0c;小米集团创始人雷军在一场备受瞩目的发布会上&#xff0c;以其一贯的激情与诚意&#xff0c;揭开了小米汽车首款车型SU7的神秘面纱。这一夜&#xff0c;不仅是小米跨足汽车行业的重要里程碑&#xff0c;更是中国智能汽车产业向前迈进的新篇章。然而…

【隐私计算实训营008——SCQL】

1.SCQL使用/集成最佳实践 目前SCQL只开放API供用户使用/集成 使用SCDBClient上手体验可以基于SCQL API开发封装白屏产品&#xff0c;或集成到业务链路中 1.1 部署系统 环境配置&#xff1a; 机器配置&#xff1a;CPU/MEM最低8C16G机构之间的网络互通 镜像&#xff1a;secret…

Golang生成UUID

安装依赖 go get -u github.com/google/uuid文档 谷歌UUID文档 示例 函数签名func NewV7() ( UUID ,错误) func (receiver *basicUtils) GenerateUUID() uuid.UUID {return uuid.Must(uuid.NewV7()) } uid : GenerateUUID()

docker部署实用的运维开发手册

下载镜像 docker pull registry.cn-beijing.aliyuncs.com/wuxingge123/reference:latestdocker-compose部署 vim docker-compose.yml version: 3 services:reference:container_name: referenceimage: registry.cn-beijing.aliyuncs.com/wuxingge123/reference:latestports:…

【日常记录】【CSS】css文字渐变擦除

文章目录 1、代码2、自定义css属性 1、代码 主要思路是&#xff1a; 1、弄一个一样的&#xff0c;覆盖到上面去 2、然后改一下文字颜色&#xff0c;改成透明&#xff0c;背景颜色改成 渐变&#xff0c;可以从透明到一个实色&#xff0c;这样就能显示出来下面的文字 3、只有 行内…

百度网站收录提交入口

百度网站收录提交入口 在网站刚建立或者更新内容后&#xff0c;及时将网站提交给搜索引擎是提高网站曝光和获取流量的重要步骤之一。百度作为中国最大的搜索引擎之一&#xff0c;网站在百度中的收录情况尤为重要。下面介绍一下如何通过百度的网站收录提交入口提交网站。 1. 百…

C#手术麻醉系统源码 大型医院手麻系统4大需求是什么?

C#手术麻醉系统源码 大型医院手麻系统4大需求是什么&#xff1f; 手术麻醉临床信息系统有着完善的临床业务功能&#xff0c;能够涵盖整个围术期的工作&#xff0c;能够采集、汇总、存储、处理、展 现所有的临床诊疗资料。通过该系统的实施&#xff0c;能够规范手麻科的工作流程…

PTA L2-045 堆宝塔

堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小&#xff0c;按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下&#xff1a; 首先准备两根柱子&#xff0c;一根 A 柱串宝塔&#xff0c;一根 B 柱用于临时叠放。把第 1 块彩虹圈…

MATLAB科研绘图与学术图表绘制从入门到精通

&#x1f482; 个人网站:【 摸鱼游戏】【神级代码资源网站】【工具大全】&#x1f91f; 一站式轻松构建小程序、Web网站、移动应用&#xff1a;&#x1f449;注册地址&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交…

Mybatis plue(二) 核心功能

核心功能 P5 条件构造器 mybatisplus支持各种复杂的where条件&#xff0c;可以满足日常开发的所有需求 wrapper就是条件构造器,wrapper就是顶层的&#xff0c; 示例&#xff1a; 查询出名字带0&#xff0c;存款大于等于1000的人的id,username,info,balance字段 Testvoid te…

Oracle Cloud公布 | 每小时 126 亿次 SQL 数据库查询

广而告之&#xff1a;2024 年数据技术嘉年华大会将于 4 月12-13 日在北京召开&#xff0c;春暖花开之际&#xff0c;数据库行业蓬勃发展之时&#xff0c;广邀天下豪杰&#xff0c;相聚北京&#xff0c;共论数据库技术发展的创新与未来。 注册&#xff1a;https://www.modb.pro/…

Adaboost集成学习 | Matlab实现基于GRU-Adaboost门控循环单元结合Adaboost集成学习时间序列预测(股票价格预测)

目录 效果一览基本介绍模型设计程序设计参考资料效果一览 基本介绍 Adaboost集成学习 | Matlab实现基于GRU-Adaboost门控循环单元结合Adaboost集成学习时间序列预测(股票价格预测) 模型设计 股票价格预测是一个具有挑战性的时间序列预测问题,可以使用深度学习模型如门控循环…

安卓Android 架构模式及UI布局设计

文章目录 一、Android UI 简介1.1 在手机UI设计中&#xff0c;坚持的原则是什么1.2 安卓中的架构模式1.2.1 MVC (Model-View-Controller)设计模式优缺点 1.2.2 MVP(Model-View-Presenter)设计模式MVP与MVC关系&#xff1a; 1.2.3 MVVM(Model—View—ViewModel ) 设计模式1.2.4 …

视觉里程计之对极几何

视觉里程计之对极几何 前言 上一个章节介绍了视觉里程计关于特征点的一些内容&#xff0c;相信大家对视觉里程计关于特征的描述已经有了一定的认识。本章节给大家介绍视觉里程计另外一个概念&#xff0c;对极几何。 对极几何 对极几何是立体视觉中的几何关系&#xff0c;描…

政务AI交互数字人推动政务“人工智能+”建设

传统的政务平台大多是单向与用户互动&#xff0c;缺乏即时反馈&#xff0c;导致用户需要花费大量时间理解信息&#xff0c;并难以提出问题得到及时解答。 AI交互数字人凭借其智能性&#xff0c;可以在政务网页、政务业务办理大厅一体机、政务APP/小程序等终端设备中&#xff0…

OSPF中配置静态路由实验简述

静态路由协议和OSPF&#xff08;开放最短路径优先&#xff09;协议是两种常见的路由协议&#xff0c;它们在路由选择和网络管理方面有一些区别。他们可以共存。 静态路由协议需要手动配置路由表&#xff0c;不会自动适应网络拓扑变化&#xff0c;适用于小型网络或者网络拓扑变化…

非关系型数据库(缓存数据库)redis的基础认知与安装

目录 一.关系型数据库和非关系型数据库 关系型数据库 非关系型数据库 关系数据库与非关系型数据库的区别 ①非关系数据 关系型数据库 非关系型数据库产生背景 数据存储流向 非关系型数据库 关系数据库 二.redis的简介 1.概念 2.Redis 具有以下几个优点: 3.Redi…

香港科技大学广州|数据科学与分析学域硕博招生宣讲会—天津大学专场

时间&#xff1a;2024年4月12日&#xff08;星期五&#xff09;14:00 地点&#xff1a;天津大学北洋园校区55楼B204 报名链接&#xff1a;https://www.wjx.top/vm/Q0cKTUI.aspx# 跨学科研究领域 *数据驱动的人工智能和机器学习 *统计学习和建模 工业和商业分析 *特定行业的数…

java 8 stream api将List<T>转换成树形结构

1、新建实体类 package com.example.springboot3.entity;import lombok.Builder; import lombok.Data;import java.util.List;Data Builder public class Menu {/*** id*/public Integer id;/*** 名称*/public String name;/*** 父id &#xff0c;根节点为0*/public Integer p…

Python深度学习034:cuda的环境如何配置

文章目录 1.安装nvidia cuda驱动CMD中看一下cuda版本:下载并安装cuda驱动2.创建虚拟环境并安装pytorch的torch_cuda3.测试附录1.安装nvidia cuda驱动 CMD中看一下cuda版本: 注意: 红框的cuda版本,是你的显卡能装的最高的cuda版本,所以可以选择低于它的版本。比如我的是11…