刷题之动态规划

前言

大家好,我是jiantaoyab,开始刷动态规划的题目了,要特别注意初始化的时候给什么值。

动态规划5个步骤

  1. 状态表示 :dp数组中每一个下标对应值的含义是什么->dp[i]表示什么
  2. 状态转移方程: dp[i] 等于什么
  3. 1 和 2 是动态规划的核心步骤,第三步是初始化,保证填表的时候不越界
  4. 填表顺序:为了保证填写当前状态的时候,所需要的状态已经计算过
  5. 返回值

第 N 个泰波那契数

image-20240327082552013

题目分析

image-20240327082930486

我们用动态规划来解决

  1. dp[i] : 表示第i个泰波那契数
  2. dp[i] = dp[i - 3] + dp[i - 2] + dp [i - 1]
  3. 初始化: dp[0] = 0; dp[1] = 1 ; dp[2] = 1;
  4. 填表顺序:从左道右
  5. 返回值:dp[n]

代码

class Solution {
public:int tribonacci(int n) {if(n == 0) return 0;if(n == 1 || n == 2) return 1;int dp[1000] = {0};dp[0] = 0, dp[1] = 1, dp[2] = 1;for(int i = 3; i <= n; i++){dp[i] = dp[i-3] + dp[i-2] + dp[i-1];}return dp[n];}
};

image-20240327085917789

优化一下,可以看到只需要三个变量也能完成这个操作。

class Solution {
public:int tribonacci(int n) {if(n == 0) return 0;if(n == 1 || n == 2) return 1;int a = 0, b = 1, c = 1, d = 0;for(int i = 3; i <= n; i++){d = a + b + c;a = b;b = c;c = d;}return d;}
};

三步问题

image-20240327090422340

image-20240327093241354

题目分析

  1. dp[i] :表示去到当前台阶有几种方法
  2. dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
  3. 初始化 dp[1] = 1; dp[2] = 2; dp[3] = 4;
  4. 填表顺序从左到右
  5. 返回值 d[n]

代码

class Solution {
public:int waysToStep(int n) {vector<int>dp(n + 1);if(n == 1 || n == 2) return n;if(n == 3) return 4;const int MOD = 1000000007;dp[1] = 1; dp[2] = 2; dp[3] = 4;for(int i = 4; i <= n; i++){dp[i] = ((dp[i-3] + dp[i-2]) % MOD + dp[i-1]) % MOD;}return dp[n];}
};

使用最小花费爬楼梯

image-20240327094348136

题目分析

image-20240327102746297

  1. dp[i]:到达 i位置的最小花费
  2. dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
  3. 初始化:dp[0] = dp[1] = 0;
  4. 填表顺序:从左到右
  5. 返回值:dp[n]

代码

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n + 1);dp[0] = dp[1] = 0;for(int i = 2; i <= n; i++){dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);}return dp[n];}
};

解码方法

image-20240328121136322

题目分析

image-20240328124124445

  1. dp[i]:是表示是 i 位置为结尾的解码方法总数
  2. dp[i] = dp[i - 1] + dp [i - 2];
  3. 初始化:dp[0] = 0 / 1 dp[1] = 0/ 1/ 2
  4. 填表顺序:从左到右
  5. 返回值:dp[n - 1]

代码

class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp (n);//初始化dp[0] = s[0] != '0';if(n == 1) return dp[0];if(s[0] != '0' && s[1] != '0') dp[1] += 1;int tmp = (s[0] - '0') * 10 + (s[1] - '0');if(tmp >= 10 && tmp <= 26) dp[1] += 1;//处理剩下的for(int i = 2; i < n; i++){//单独一个字符if(s[i] != '0') dp[i] += dp[i - 1];//2个字符int tmp = (s[i - 1] - '0') * 10 + (s[i] - '0');if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];}return dp[n - 1];}
};

优化代码

image-20240328132736524

class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp (n + 1); //初始化dp[0] = 1;dp[1] = s[1 - 1] != '0';  //处理剩下的for(int i = 2; i <= n; i++){//单独一个字符if(s[i - 1] != '0') dp[i] += dp[i - 1];//2个字符int tmp = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];}return dp[n];}
};

不同路径

image-20240328133027939

题目分析

image-20240328142217131

  1. dp[i] [j]:走到 i,j 位置有多少种方式
  2. dp[i] [j] = dp[i] [j - 1] + dp[i - 1] [j];
  3. 初始化:新增加一列和一行
  4. 填表顺序:从上到下,左到右填表
  5. 返回值:dp[m] [n]

代码

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

不同路径 II

image-20240328142046409

题目分析

  1. dp [i] [j] : 到达i,j这个位置有多少种方法
  2. dp [i] [j] = dp[i - 1] [j] + dp [i] [j - 1]
  3. 初始化:dp[1] [0] = 1;
  4. 填表顺序:从上到下,从左到右
  5. 返回值: dp[m] [n]

代码

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(), n = obstacleGrid[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));//初始化dp[1][0] = 1;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(obstacleGrid[i - 1][j - 1] != 1)dp[i][j] = dp[i - 1][j] + dp[i][j -1];}}return dp[m][n];} 
};

珠宝的最高价值

image-20240329083509134

题目分析

  1. dp [i] [j] : 到达i,j这个位置的最高价值
  2. dp [i] [j] =max(dp[i-1] [j], dp[i] [j-1]) + frame[i-1] [j-1];
  3. 初始化:默认都是0不用初始化
  4. 填表顺序:从上到下,从左到右
  5. 返回值: dp[m] [n]

代码

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {int m = frame.size(), 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-1][j], dp[i][j-1]) + frame[i-1][j-1];}return dp[m][n];}
};

下降路径最小和

image-20240329090000519

题目分析

  1. dp[i] [j] : 到达i,j位置的最小下路径
  2. dp[i] [j] : min(dp[i+1] [j-1], dp[i+1] [j+1], dp[i+1] [j]) + matrix[i-1] [j - 1]
  3. 初始化:多给1行 和2列
  4. 填表顺序:从上到下,从左到右
  5. 返回值: 最后一行的最小值

image-20240329093844878

代码

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));for(int j = 0; j < n + 2; j++) dp[0][j] = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i-1][j+1]) + matrix[i-1][j-1];}}      //返回值int ret = INT_MAX;for(int j = 1; j <= n; j++){ret = min(ret, dp[n][j]);}return ret;}
};

最小路径和

image-20240329094117164

代码

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));dp[1][0] = dp[0][1] = 0; for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++){dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];}return dp[m][n];}
};

地下城游戏(反着来)

image-20240329102706154

题目分析

image-20240329105223745

  1. dp[i] [j] : 从i,j位置出发,到达终点所需要的最低

  2. dp[i] [j] = min(dp[i] [j + 1], dp[i + 1] [j]) - dungeon[i] [j];

  3. 初始化 dp[m +1] [n -1] = dp [m - 1] [n + 1] = 1;

  4. 填表顺序:从下到上,从右到左

  5. 返回值: dp[0] [0]

代码

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size(), n = dungeon[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));//初始化dp[m][n -1] = dp [m - 1][n] = 1;for(int i = m - 1; i >= 0; i--)for(int j = n - 1; j >= 0; j--){dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];dp[i][j] = max(1, dp[i][j]); //如果血包很大,会出现负数,这里取1就是最低血}return dp[0][0];}
};

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

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

相关文章

用grafana+prometheus+cadvisor监控容器指标数据,并查询当前容器的网速网络用量

前言 整理技术&#xff0c;在这篇文章中&#xff0c;将会搭建grafanaprometheuscadvisor监控容器&#xff0c;并使用一个热门数据看板&#xff0c;再监控容器的性能指标 dashboard效果 这个是node-exporter采集到的数据&#xff0c;我没装node-exporter&#xff0c;而且这也…

第三十二天-Django模板-DTL模板引擎

目录 1.介绍 2. 使用 1.配置jinja2 2.DTL模板变量使用 3.与jinja2区别 4.模板标签使用 1.循环 2.条件控制 3.注释 4.url解析 5.显示时间 5.模板的基础与包含 6.过滤器 内置过滤器 自定义过滤器 1.介绍 2. 使用 1.配置jinja2 2.DTL模板变量使用 与jinja2语法相似…

短视频矩阵系统--技术3年源头迭代

短视频矩阵系统核心技术算法主要包括以下几个方面&#xff1a; 1. 视频剪辑&#xff1a;通过剪辑工具或API从各大短视频平台抓取符合要求的视频。这些视频通常符合某些特定条件&#xff0c;如特定关键词、特定时间段发布的视频、视频点赞评论转发等数据表现良好的视频。 2. 视…

vue3+threejs新手从零开发卡牌游戏(二十一):添加战斗与生命值关联逻辑

首先将双方玩家的HP存入store中&#xff0c;stores/common.ts代码如下&#xff1a; import { ref, computed } from vue import { defineStore } from piniaexport const useCommonStore defineStore(common, () > {const _font ref() // 字体const p1HP ref(4000) // 己…

[Python GUI PyQt] PyQt5快速入门

PyQt5快速入门 PyQt5的快速入门0. 写在前面1. 思维导图2. 第一个PyQt5的应用程序3. PyQt5的常用基本控件和布局3.1 PyQt5的常用基本控件3.1.1 按钮控件 QPushButton3.1.2 文本标签控件 QLabel3.1.3 单行输入框控件 QLineEdit3.1.4 A Quick Widgets Demo 3.2 PyQt5的常用基本控件…

大模型重塑电商,淘宝、百度、京东讲出新故事

配图来自Canva可画 随着AI技术日渐成熟&#xff0c;大模型在各个领域的应用也越来越深入&#xff0c;国内互联网行业也随之进入了大模型竞赛的后半场&#xff0c;开始从“百模大战”转向了实际应用。大模型从通用到细分垂直领域的跨越&#xff0c;也让更多行业迎来了新的商机。…

c语言游戏实战(7):扫雷

前言&#xff1a; 扫雷是一款经典的单人益智游戏&#xff0c;它的目标是在一个方格矩阵中找出所有的地雷&#xff0c;而不触碰到任何一颗地雷。在计算机编程领域&#xff0c;扫雷也是一个非常受欢迎的项目&#xff0c;因为它涉及到许多重要的编程概念&#xff0c;如数组、循环…

3D人体姿态估计项目 | 从2D视频中通过检测人体关键点来估计3D人体姿态实现

项目应用场景 人体姿态估计是关于图像或视频中人体关节的 2D 或 3D 定位。一般来说&#xff0c;这个过程可以分为两个部分&#xff1a;(1) 2D 视频中的 2D 关键点检测&#xff1b;(2) 根据 2D 关键点进行 3D 位姿估计。这个项目使用 Detectron2 从任意的 2D 视频中检测 2D 关节…

海豚【货运系统源码】货运小程序【用户端+司机端app】源码物流系统搬家系统源码师傅接单

技术栈&#xff1a;前端uniapp后端vuethinkphp 主要功能&#xff1a; 不通车型配置不通价格参数 多城市定位服务 支持发货地 途径地 目的地智能费用计算 支持日期时间 预约下单 支持添加跟单人数选择 支持下单优惠券抵扣 支持司机收藏订单评价 支持订单状态消息通知 支…

FANUC机器人故障诊断—报警代码更新(三)

FANUC机器人故障诊断中&#xff0c;有些报警代码&#xff0c;继续更新如下。 一、报警代码&#xff08;SRVO-348&#xff09; SRVO-348DCS MCC关闭报警a&#xff0c;b [原因]向电磁接触器发出了关闭指令&#xff0c;而电磁接触器尚未关闭。 [对策] 1.当急停单元上连接了CRMA…

备考ICA----Istio实验14---出向流量管控Egress Gateways实验

备考ICA----Istio实验14—出向流量管控Egress Gateways实验 1. 发布测试用 pod kubectl apply -f istio/samples/sleep/sleep.yaml kubectl get pods -l appsleep2. ServiceEntry 创建一个ServiceEntry允许流量访问edition.cnn.com egressgw/edition-ServiceEntry.yaml api…

使用anime.js实现列表滚动轮播

官网&#xff1a;https://animejs.com/ html <div id"slide1"><div class"weather-item" v-for"item in weatherList"><div><img src"../../images/hdft/position.png" alt"">{{item.body.cityInf…

Topaz Gigapixel AI for Mac 图像放大软件

Topaz Gigapixel AI for Mac是一款专为Mac用户设计的智能图像放大软件。它采用了人工智能技术&#xff0c;特别是深度学习算法&#xff0c;以提高图像的分辨率和质量&#xff0c;使得图像在放大后仍能保持清晰的细节。这款软件的特点在于其能够将低分辨率的图片放大至高分辨率&…

基于SSM+Jsp+Mysql的美食推荐管理系统

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

【学习】JMeter和Postman两种测试工具的主要区别有哪些

Postman和JMeter都是常用的API测试工具&#xff0c;但它们之间存在一些不同之处。以下是Postman和JMeter的主要区别&#xff1a; 语言支持 Postman是一个基于Chrome的应用程序&#xff0c;因此它使用JavaScript作为编程语言。这意味着你可以使用JavaScript来编写测试脚本和断…

农村分散式生活污水分质处理及循环利用技术指南

标准已完成意见征集&#xff1a; 本文件给出了农村分散式生活污水分质处理及循环利用的总则、污水收集、污水分质处理、资源化利用、利用模式、运维管理等的指导。 本文件适用于农村分散式生活污水分质处理及循环利用的设施新建、扩建和改建工程的设计、施工与运维。 注:本文件…

13-API风格(下):RPCAPI介绍

RPC在Go项目开发中用得也非常多&#xff0c;需要我们认真掌握。 RPC介绍 根据维基百科的定义&#xff0c;RPC&#xff08;Remote Procedure Call&#xff09;&#xff0c;即远程过程调用&#xff0c;是一个计算机通信协议。该协议允许运行于一台计算机的程序调用另一台计算机…

记录一个写自定义Flume拦截器遇到的错误

先说结论&#xff1a; 【结论1】配置文件中包名要写正确 vim flume1.conf ... a1.sources.r1.interceptors.i1.type com.atguigu.flume.interceptor.MyInterceptor2$MyBuilder ... 标红的是包名&#xff0c;表黄的是类名&#xff0c;标蓝的是自己加的内部类名。这三个都…

使用CRXjs、Vite、Vue 开发 Chrome 多页面插件,手动配置 vite.config.ts 和 manifest.json 文件

一、使用CRXjs、Vite、Vue 开发 Chrome 多页面插件&#xff0c;手动配置 vite.config.ts 和 manifest.json 文件 一、创建 Vue 项目 1. 使用 Vite 创建 Vue 项目 npm create vitelatest # npm yarn create vite # yarn pnpm create vite # pnpm选择 Vue 和 TS 进入项目…

Qt 使用QMYSQL 报错:driver not loaded

目录 0、导读1、下载mysql驱动2、拷贝mysql驱动文件拷贝到qt环境下 0、导读 使用Qmysql, 调用远程数据&#xff0c;如果报这个错误&#xff1a;driver not loaded&#xff08;驱动未加载&#xff09;&#xff0c;一般是缺少libmysql.dll或者libmysql.lib文件。这里提供一个网址…