代码随想录算法训练营DAY38|C++动态规划Part.1|动态规划理论基础、509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯

本文主要是介绍代码随想录算法训练营DAY38|C++动态规划Part.1|动态规划理论基础、509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 动态规划理论基础
    • 什么是动态规划
    • 动态规划的解题步骤
      • DP数组以及下标的含义
      • 递推公式
      • DP数组初始化
      • DP数组遍历顺序
      • 打印DP数组
      • 动态规划五部曲
    • 动态规划应该如何debug
  • 509.斐波那契数
    • 什么是斐波那契数列
    • 动态规划五部曲
      • 确定dp数组下标以及含义
      • 确定递推公式
      • dp数组如何初始化
      • 确定遍历顺序
      • 打印DP数组
    • 代码实现
    • CPP代码
  • 70.爬楼梯
    • 题意分析
    • 动规五部曲
      • 确定dp数组下标以及含义
      • 确定递推公式
      • dp数组如何初始化
      • 确定遍历顺序
      • 打印DP数组
    • 扩展题
    • CPP代码
  • 746.使用最小花费爬楼梯

在这里插入图片描述

动态规划理论基础

什么是动态规划

动态规划(Dynamic Programming, DP),如果某一个问题有很多重叠子问题,这样往往是用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的。

对于刷题来说就抓住一句话:

动规是由前一个状态推导出来的,而贪心是从局部直接选出最优的

动态规划的解题步骤

在全面总结动态规划解题步骤前,同时也是做动态规划类题目之前,我们要先搞明白以下几个问题:

DP数组以及下标的含义

有很多类问题有一个二维dp数组,其中的行、列的含义一定要搞清楚;同理一维dp数组中的值又是什么呢?在写代码前,一定要搞明白这是什么意思。

递推公式

动态规划递推公式仅仅是一部分,而不是只要掌握了递推公式,动规就变得简单了。

DP数组初始化

dp数组如何初始化其实紧贴着dp数组以及下标含义,如果dp数组里是什么,各个维度含义是什么,那dp数组的初始化更加无从谈起了。

DP数组遍历顺序

对于背包类问题,遍历顺序是非常有讲究的,所以每道题一定要弄清他们的遍历顺序。

打印DP数组

如果题目通过不了,首先应该考虑是不是dp数组出了问题,我们应该吧dp数组打印出来看是否符合预期

动态规划五部曲

一定要仔细分析上述的五大问题

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

动态规划应该如何debug

做动规的题目,写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍,心中有数,确定最后推出的是想要的结果

然后再写代码,如果代码没通过就打印dp数组,看看是不是和自己预先推导的哪里不一样。

这样才是一个完整的思考过程,而不是一旦代码出问题,就毫无头绪的东改改西改改,最后过不了,或者说是稀里糊涂的过了

这里给出卡哥写的自我debug的灵魂三问:

  • 这道题目我举例推导状态转移公式了么?
  • 我打印dp数组的日志了么?
  • 打印出来了dp数组和我想的一样么?

509.斐波那契数

力扣题目链

文章链接:509.斐波那契数列

视频链接:手把手带你入门动态规划 | leetcode:509.斐波那契数

状态:迭代法还是会写一写

什么是斐波那契数列

动态规划五部曲

确定dp数组下标以及含义

dp[i]表示第i个斐波那契数值为dp[i]

确定递推公式

斐波那契数的递推公式很明显: d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] dp[i] = dp[i - 1] + dp[i - 2] dp[i]=dp[i1]+dp[i2]

dp数组如何初始化

斐波那契的初始化也很简单 [ 0 , 1 , 1 , 2 , 3 , 5 , 8 ] [0, 1, 1, 2, 3, 5, 8] [0,1,1,2,3,5,8]

由数学归纳可知: d p [ 0 ] = 0 ; d p [ 1 ] = 1 ; dp[0] = 0; dp[1] = 1; dp[0]=0;dp[1]=1;

在很多题目中,dp数组的初始化往往也依赖于递推公式

确定遍历顺序

本题中,遍历顺序从前向后即可。(有一些题目从后向前遍历;有一些题目两层for循环,其先先后顺序也有说法)

打印DP数组

这个主要是用来debug的

代码实现

vector<int> dp(n+1);
//初始化
dp[0] = 0; dp[1] = 1;
for (i = 2; i <= n; i++)dp[i] = dp[i-1] + dp[i-2];
return dp[n];

对状态进行压缩,只需要维护两个数值就可以了,不需要记录整个序列.代码可以缩减为

int fib(int N){if (N <= 1) return N;int dp[2];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++){int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];
}

时间复杂度为O(2^n)的递归解法:

int fib(int N){if (N < 2) return N;return fib(N - 1) + fib(N - 2);
}

CPP代码

class Solution {
public:int fib(int N) {if (N <= 1) return N;vector<int> dp(N + 1);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[N];}
};
//只维护两个数值
class Solution {
public:int fib(int N) {if (N <= 1) return N;int dp[2];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};
//递归
class Solution {
public:int fib(int N) {if (N < 2) return N;return fib(N - 1) + fib(N - 2);}
};

70.爬楼梯

力扣题目链接

文章讲解:70.爬楼梯

视频讲解:带你学透动态规划-爬楼梯|LeetCode:70.爬楼梯)

状态:

题意分析

如果对于一个n阶台阶,每次你可以爬 12 个台阶。有多少种不同的方法可以爬到楼顶。

如果台阶一共只有1阶,一共只有1

如果台阶有2阶,一共有2

如果台阶有3阶,一共有3

如果台阶有4阶,一共有5

本质上,当前台阶有几种方法,主要依赖于前两个状态

其实这就是递推关系。这种递推关系可以用动态规划来解决。

动规五部曲

确定dp数组下标以及含义

dp[i],达到i阶有dp[i]种方法。

确定递推公式

dp[i - 2]表示达到i-2阶有dp[i - 2]种方法

dp[i - 1]表示达到i-1阶有dp[i - 1]种方法

dp[i]表示达到i阶有dp[i]种方法

d p [ i ] = d p [ i − 2 ] + d p [ i − 1 ] dp[i] = dp[i-2]+dp[i-1] dp[i]=dp[i2]+dp[i1]

dp数组如何初始化

从递推公式可以看出,最重要的就是初始化数组的前几位

dp[0] = 1还是dp[0] = 0

因为我们dp[2] = 2,从递推公式出发,dp[0]应该初始化成1。同时题目中也说过,n为正整数

在代码随想录的代码中,是不初始化0的,而是直接初始化dp[2]dp[1]

确定遍历顺序

从前向后遍历即可

打印DP数组

用于debug

其实本质上,从上文论述的规律可以看出,其实本题就是一个斐波那契数列

扩展题

一步可以走m个台阶,爬n阶的楼梯有多少种方法。

词题可以用完全背包的思路来解决。

CPP代码

//还是只维护两个数组
class Solution {
public:int climbStairs(int n) {if (n <= 3) return n;int dp[2];dp[0] = 1; dp[1] = 2;for (int i = 3; i <= n; ++i) {int cur = dp[0] + dp[1];dp[0] = dp[1];dp[1] = cur;}return dp[1];}
};

746.使用最小花费爬楼梯

力扣题目链接

文章讲解:746.使用最小花费爬楼梯

视频讲解:动态规划开更了!| LeetCode:746. 使用最小花费爬楼梯

状态:相较于前两个题目,难度一下就上来了,我个人感觉是贪心和动态规划的结合。

在题目描述中,我们可以选择从下标为0或下标为1的台阶开始爬楼梯。

思路

dp数组含义

想给出结论,本题仍然只需要一个一维的dp数组,其下标记录我们到达了哪个台阶,其中的值就是体力的最小消耗。

以上的推导都是怎么来的呢?

要求的是爬到楼顶,那么我们dp数组应该得用下标来表示我们爬的位置,看是不是到楼顶了;

然后我们要求一个最小消耗,那么我们的dp数组刚好可以存到达该层的一个消耗,刚好逻辑就闭环。

综上:

dp[i]表示到达i位置所需要的花费为dp[i]

递推公式

本题中我们要求的就是dp[i],那么如何跳到dp[i]呢?我们可以从dp[i-1]跳一步到dp[i],也可以从dp[i-2]跳两步到dp[i]

如果从dp[i-1]跳到dp[i]的话,所需要的花费是dp[i-1] + cost[i-1]

如果从dp[i-2]跳到dp[i]的话,所需要的花费是dp[i-2] + cost[i-2]

dp[i]表示到达i位置所需要的花费为dp[i]

显然递推公式为: d p [ i ] = m i n ( d p [ i − 1 ] + c o n s t [ i − 1 ] , d p [ i − 2 ] + c o n s t [ i − 2 ] ) dp[i] = min(dp[i-1] + const[i-1], dp[i-2] + const[i-2]) dp[i]=min(dp[i1]+const[i1],dp[i2]+const[i2])

初始化

很明显,本题只要初始化了dp[1]dp[0]就可以把递推公式打通了。

//题意表明了,可以选择从0层或者从第1层开始跳
dp[0] = 0;	//到达0位置最小花费为0
dp[1] = 0;	//到底1位置最小花费也是0. 因为我们可以选择嘛

遍历顺序

从零往后去遍历

因为是模拟台阶,而且dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了。

打印dp数组

打印出来看是不是和我们预想的一样

CPP代码

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {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()];}
};//只维护两个数字
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int dp0 = 0;int dp1 = 0;for (int i = 2; i <= cost.size(); i++) {int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);dp0 = dp1; // 记录一下前两位dp1 = dpi;}return dp1;}
};

这篇关于代码随想录算法训练营DAY38|C++动态规划Part.1|动态规划理论基础、509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/940205

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个