【蓝桥杯速成】| 5.动态规划

server/2025/3/18 12:32:32/

学习资料

代码随想录

动态规划五部曲

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

简单题

509. 斐波那契数 - 力扣(LeetCode)

70. 爬楼梯 - 力扣(LeetCode)

可以先尝试自己用dp五部曲,把原来的递归方法转为动态规划

动态规划通过把结果保存在dp数组中,避免了递归中的重复工作

从而降低了代码的时间复杂度

难度升级!!!

题目一:使用最小花费爬楼梯

问题描述

746. 使用最小花费爬楼梯 - 力扣(LeetCode)

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1:

输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。

解题步骤

首先需要明确一下题意,题目要求可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯

那么就是说我们一开始站在0/1这节台阶上是0花费的

最终我们的目标有两个

一是跳到楼梯顶部(第i+1个台阶,不是第i个台阶!不然为什么要有cost[i]呢你说?)

二是实现最低花费

接着开始使用动态规划五部曲,格式化做题有助于前期的理解与掌握 

1.确定dp数组(dp table)以及下标的含义

这里肯定选用一维数组dp[i]

i代表第i节台阶,dp[i]存放的是到达第i节台阶所需的最小花费

dp[i]//到达第i节台阶的最小花费

2.确定递推公式

根据跳台阶的简单题,我们可以知道dp[i]的值与dp[i-1],dp[i-2],cost[i-1],cost[i-2]有关,

因为第 i 节台阶可以从第 i - 1 节台阶跳一步到达,也可以从第 i - 2 节台阶直接跳两级到达

dp[i-1]+cost[i-1]代表在到达第i-1节台阶需要的最小花费为dp[i-1],继续到达第i节还需要花费cost[i-1]

但由于最后我们需要的是最小花费,所以dp[ i ] 的值应该取这两者的最小值

即 dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3.dp数组如何初始化

初始化就是要找到最初状态进行赋值

很显然最初状态就是起跑线嘛

dp[0]=0,dp[1]=1

4.确定遍历顺序

这一题没什么弯弯绕绕的,从头开始跳就完了

for(int i=2;i<=cost.size()+1;i++)

5.举例推导dp数组

这一步可以用在检查代码问题,这里不多赘述

组合这5步,得到

vector<int> dp(cost.size()+1);
dp[0]=0;
dp[1]=0;
for(int i=2;i<=cost.size();i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[cost.size()];

 就这么简单!恭喜获得dp小试牛刀称号一枚!


题目二:不同路径

问题描述

62. 不同路径 - 力扣(LeetCode) 

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

解题步骤

动态规划五部曲

1.确定dp数组(dp table)以及下标的含义

由于是m x n的网格,我们应该也用二维数组作为dp的数据结构

那么dp[i][j]就是走到当前格(第i行第j列)的路径数

最后需要返回的是dp[m-1][n-1]

vector<vector<int>> dp(m,vector<int> n);//注意二维数组的定义!

2.确定递推公式

按照移动规律,每次只能向下或者向右移动一步

那么[ i ][ j ]这一格可以从[ i-1 ][ j ]走过来,也可以从[ i ][ j-1 ]走过来

所以

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

容易出现的误区:认为dp[i][j]=(dp[i-1][j]+1)+(dp[i][j-1]+1)

这样做就是没想明白dp数组的真实含义,我们不是在统计走了几格

而是在统计路径数,从[ i-1 ][ j ]到[ i ][ j ]这一步并不是多了一个新路径,而是原路径的延续而已

路径的增多就只体现在这两种方案选择加起来

 

 3.dp数组如何初始化

从[0][0]开始行动!

那么我们首先想到的肯定是 dp[0][1]=1;dp[1][0]=1

但仔细思考一下,只能向下或者向右走

那我们需要初始化的其实是第一行和第一列的所有元素

他们的值都应该为1,只能一条道走到黑!

for(int i=0;i<m;i++){

       dp[i][0]=1;

}

for(int j=0;j<n;j++){

        dp[0][j]=1;

}

 4.确定遍历顺序

遍历顺序应该接着初始化内容继续往下生成,又要保证每一格格子都填上

所以应该从1开始

for(int i=1;i<m;i++){

        for(int j=1;j<n;j++{

 5.举例推导dp数组

 这一步还是看情况使用啦

那么整体代码如下:

class Solution {
public:int uniquePaths(int m, int n) {//定义 dp[i][j]指走到这个格有几种路径vector<vector<int>> dp(m, vector<int>(n));//初始化//需要给第一行第一列都得初始化为1,才能确保它按照规则走!//dp[0][0]=0;for(int i=0;i<m;i++){dp[i][0]=1;}for(int j=0;j<n;j++){dp[0][j]=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-1][n-1];}
};

 做完这一题可以尝试一下进阶版:

63. 不同路径 II - 力扣(LeetCode)

加了一点障碍,整体思路是大差不差的!

只是要在关键处加入对障碍的判断即可


题目三:整数拆分

问题描述

343. 整数拆分 - 力扣(LeetCode)

给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

  • 2 <= n <= 58

解题步骤

初看这一题,我认为就是往拆成尽可能大的两个数(最好是一人一半)进行相乘

这样后面的数字可以利用前面的数字继续两两相乘即可

但仔细一看,将其拆成k个正整数和,那么就不止掰两半,并且掰三份还真的有可能更大

比如示例2:输入10,如果拆成两个5,两数之积才25,拆成3 3 4,乘积就是36

虽然拆分思路不对,但是这些数字取最大乘积肯定还是存在递推关系的

那么我们就还是用动态规划五部曲一步一步来!

但是此处我认为可以调换一下五部曲顺序,先把我们能做的做好!

1.确定dp数组(dp table)以及下标的含义

没有任何二维的特征,肯定用一维数组dp[ i ]

i 表示当前值,dp[ i ]表示这个数拆分后的最大乘积

我们需要不断拆分i,去取得最大乘积

vector<int> dp(n+1);

 2.dp数组如何初始化

初始化这一步既简单又关键

我们只需要想想最开始的几个有无特殊,做一个设置即可

对于0,1不能拆分为正整数,我们不做初始化

所以只有2需要提前设定一下!

dp[2]=1

3.确定遍历顺序

因为拆分有多种情况,所以我们需要在范围内遍历所有情况

那么设置内外两层循环

外循环用于遍历i

内循环用于拆分,用 j 遍历所有结果

for(int i=3;i<=n;i++){

        for(int j=1;j<i;j++){

4.确定递推公式

这一块是本题的重点!

按照前面的逻辑dp[ i ]  = dp[ j ] * dp[ i -j ]

就是把i拆成了 j,i-j两个数,然后当前值拆分后的乘积 应该是这两者最大乘积的 乘积

但这样有点思维定势了,我们得到乘积的方法不止这一个

直接相乘也是它的乘积 dp[i] = j *(i-j) ,我们并不能确定哪个更大

可能直接想有点抽象,我们举例来说

i=4,j=2 //4被拆成2*2的情况

dp[4] = dp[2] * dp[2]  = 1*1=1

dp[4] = 2 * 2 =4

所以我们需要在这两种方案中取最大值

dp[i] = max(dp[ j ] * dp[ i-j ]), j * ( i - j ))

ok,想到这是不是就觉得结束了呢?run一下就发现完全对不上!

因为我们还忽略了两件事情,

第一件:对于一个i 我们需要决出唯一的最大值,

但我们并没有在所有方案中找最大值啊

所以递推公式应该改为

dp[i] = max ( max(dp[ j ] * dp[ i-j ]), j * ( i - j )) , dp[i])//括号里的dp[i]指的是上一个方案的最大值!

第二件:使用dp就代表我们对该数字进行了拆分

但一个数字不需要两遍同时拆分,这里会有重复

例如:5可以分为 1和4,2和3,3和2,4和1

 j 值不断改变是可以得到所有情况的(实际上前两种和后两种一样嘛)

那么也就是说dp[ i -j ]会对1,2,3,4都进行dp操作(执行dp就是开始拆分,经过递推就会有多种拆分方法生成)

那么重复的dp[j]就没有必要

所以最后应该改为

dp[i]=max(max(j*(i-j),j*dp[i-j]),dp[i]);

ok到这一步我们的程序就没有问题啦

完整代码如下:

class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1);//第i个数字拆分后的最大乘积为dp[i]//初始化//0,1,不可拆分为正整数,没有初始化意义!dp[2]=1;//遍历for(int i=3;i<=n;i++){//拆分for(int j=1;j<i;j++){//递推公式dp[i]=max(max(j*(i-j),j*dp[i-j]),dp[i]);//dp[i]=max(j*(i-j),j*dp[i-j]);}}return dp[n];}
};

 


http://www.ppmy.cn/server/175953.html

相关文章

网络层协议

目录 一、网段划分的发展过程 &#xff08;1&#xff09;固定长度的网络号 &#xff08;2&#xff09;子网掩码---网络号长度不再固定 二、公有IP和私有IP &#xff08;1&#xff09;私有IP &#xff08;2&#xff09;NAT技术 三、IP协议报头 分片操作 四、查看一下li…

Windows 图形显示驱动开发-WDDM 3.0功能- 硬件翻转队列(一)

WDDM 3.0 之前的翻转队列模型 许多新式显示控制器支持对按顺序显示的多个帧排队的能力。 从 WDDM 2.1 开始&#xff0c;OS 支持将在下一个 VSync 中显示的多个未完成的翻转覆盖请求。 显示微型端口驱动程序 (KMD) 通过 DXGK_DRIVERCAPS 中的 MaxQueuedMultiPlaneOverlayFlipVS…

算法016——最小覆盖子串

力扣——最小覆盖子串&#xff08;点击跳转&#xff09; 分析题目 我们先随便从一个位置开始&#xff0c;让 right 右移&#xff0c;直到找到符合题目的位置停下 之后&#xff0c;让 left 右移&#xff0c;此时会出现两种情况 仍然符合要求&#xff0c;right 不需要动不符合…

MiddleVR for Unity插件

MiddleVR for Unity插件 “Unity为一款3D应用程序开发工具&#xff0c;使您能够专注于创造令人惊叹的3D应用。”MiddleVR是一个完美的Unity插件&#xff0c;可在几分钟内为你的Unity应用程序带来身临其境的性能&#xff01; MiddleVR For Unity增加了以下功能&#xff1a; • …

TypeScript + Vue:类风格组件如何引领前端新潮流?

&#x1f680; TypeScript Vue&#xff1a;用类风格组件打造“假货比对”神器&#xff01;&#x1f31f; 2025 年&#xff0c;前端开发早已进入“类型安全 模块化”的黄金时代。TypeScript (TS) 的类风格组件正在席卷 Vue 社区&#xff0c;为开发者带来更优雅、更强大的编码体…

无人机+无人车+机器狼+DeepSeek:智能化设备集群技术详解

无人机、无人车、机器狼与DeepSeek的结合代表了智能化设备集群技术的重要发展方向。以下是对这一技术的详细解析&#xff1a; DeepSeek技术概述 DeepSeek是一种基于深度学习和数据挖掘技术的智能搜索与分析系统。它通过深度学习模型理解数据的上下文语义&#xff0c;实现更智…

Bash语言的语法

Bash语言的魅力&#xff1a;探秘命令行的力量 引言 在现代计算机科学的领域中&#xff0c;编程语言和脚本语言的使用已经变得不可或缺。每一种语言都有其独特的魅力和用武之地。在众多编程语言中&#xff0c;Bash&#xff08;Bourne Again SHell&#xff09;作为一种强大的脚…

Chat2DB:让数据库管理像聊天一样简单

数据库工具的痛点与破局 在数据爆炸的时代&#xff0c;数据库管理工具已成为企业高效运营的刚需。然而&#xff0c;传统工具如Navicat、DBeaver虽功能强大&#xff0c;却让非技术人员和SQL新手望而却步。复杂的界面、繁琐的手动操作、晦涩的语法规则&#xff0c;成为横亘在数据…