算法沉淀 —— 动态规划篇(斐波那契数列模型)

2024-03-25 07:52

本文主要是介绍算法沉淀 —— 动态规划篇(斐波那契数列模型),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法沉淀 —— 动态规划篇(斐波那契数列模型)

  • 前言
  • 一、第 N 个泰波那契数
  • 二、三步问题
  • 三、使用最小花费爬楼梯
  • 四、解码方法

前言

几乎所有的动态规划问题大致可分为以下5个步骤,后续所有问题分析都将基于此

  • 1.、状态表示:通常状态表示分为以下两种,其中更是第一种为主。

    • 以i为结尾,dp[i] 表示什么,通常为代求问题(具体依题目而定)
    • 以i为开始,dp[i]表示什么,通常为代求问题(具体依题目而定)
  • 2、状态转移方程
    *以上述的dp[i]意义为更具, 通过最近一步来分析和划分问题,由此来得到一个有关dp[i]的状态转移方程。

  • 3、dp表创建,初始化

    • 动态规划问题中,如果直接使用状态转移方程通常会伴随着越界访问等风险,所以一般需要初始化。而初始化最重要的两个注意事项便是:保证后续结果正确,不受初始值影响;下标的映射关系
    • 初始化一般分为以下两种:
      • 直接初始化开头的几个值。
      • 一维空间大小+1,下标从1开始;二维增加一行/一列
  • 4、填dp表、填表顺序:根据状态转移方程来确定填表顺序。

  • 5、确定返回值

一、第 N 个泰波那契数

【题目链接】:1137. 第 N 个泰波那契数
【题目】:
在这里插入图片描述
【分析】:
 题目要第n个斐波那契数,我们令dp[i]表示第i个斐波那契数。题目中以及给出了状态转移方程:dp[i] = dp[i-1] + dp[i-2] +dp[i-3]。但我们发现当i为0、1、2时显然状态转移方程错误,还会越界访问。所以我们仅需将前3个元素特殊处理,然后在从下标2开始填dp表。最后返回结果即可!
【代码实现】:

class Solution {
public:int tribonacci(int n) {if(n == 0)return 0;else if(n == 1 || n == 2)return 1;//创建dp表vector<int> dp(n + 1);//初始化dp[0] = 0, dp[1] = dp[2] = 1;//填表for(int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];return dp[n];}
};

二、三步问题

【题目链接】:面试题 08.01. 三步问题

【题目】:
 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。

【分析】:
 我们可以定义dp[i]表示小孩走到i阶台阶时上楼方式的最大值。由题目可知,小孩一次可以走1阶、2阶、3阶。所以我们容易得到状态转移方程为dp[i] = dp[i-1] + dp[i-2] + dp[i-3](题目明确表示结果肯过大,记得模1000000007!!)。
 显然你以及观察到当i <=3时,状态转移方程不适应。所以我们可以提前将前3个dp表中的值进行初始化;然后在从左往右依次填表。最后返回结果即可!!

【代码实现】:

class Solution {
public:int waysToStep(int n) {//特殊处理if(n == 1)return 1;else if(n == 2)return 2;else if(n == 3)return 4;const int DEL = 1000000007;vector<int> dp(n + 1);//创建dp表,多开一个空间,让下标对应//初始化dp[1] = 1, dp[2] = 2, dp[3] = 4;//填表for(int i = 4; i <= n; i++)dp[i] = (dp[i - 1] + (dp[i - 2] + dp[i - 3]) % DEL) % DEL;return dp[n];}
};

三、使用最小花费爬楼梯

【题目链接】:746. 使用最小花费爬楼梯
【题目】:
 给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

实例:
在这里插入图片描述

【分析】
 我们可以用dp[i]变化到达下标为i的台阶时的最低花费。题目中指出,一步可选择向上爬一个或者两个台阶。所以dp[i]必然是从i-1阶或i-2阶台阶爬上来的,易得状态转移方程为dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
 显然当i为0、1时需要单独处理(处理为0)。但C++vector创建dp表时,已经将所有数据初始化为0,所以此步不需要单独实现。然后就是从下标2开始,从左往右依次填dp表了。最后返回结果即可!!

【代码实现】:

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {//创建dp表int n = cost.size();vector<int> dp(n + 1);//填表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];}
};

四、解码方法

【题目链接】:91. 解码方法
【题目】:
一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:

“AAJF” ,将消息分组为 (1 1 10 6)
“KJF” ,将消息分组为 (11 10 6)
注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的非空字符串 s ,请计算并返回解码方法的总数 。题目数据保证答案肯定是一个32位的整数。

【分析】:
 我们定义dp[i]表示从下标[0, i]的子字符串的解法方式总数。显然解码到dp[i]的最近一步分为:从[0,i-1] 加s[i],如果s[i]合法,此时d[i] += dp[i-1];从[0, i-2] 加s[i-1,i],如果s[i-1, i]合法,此时dp[i] += dp[i-2]。所以我们可以得到对应的状态转移方程。(具体看代码)
 显然我们需要将dp[1]、dp[2]单独处理,就不多说了。然后从左往右依次填表,最后返回结果!!
在这里插入图片描述

【代码实现】:

class Solution {
public:int numDecodings(string s) {int n = s.size();//创建dp表vector<int> dp(n);//初始化dp[0] = s[0] != '0';if(n == 1)return dp[0];if(s[0] != '0' && s[1] != '0')dp[1]++;int tmp = (s[0] - '0') * 10 + s[1] - '0';if(tmp >= 10 && tmp <= 26)dp[1]++;//填表for(int i = 2; i < n; i++){if(s[i] != '0')dp[i] += dp[i - 1];int tmp = (s[i - 1] - '0') * 10 + s[i] - '0';if(tmp >= 10 && tmp <= 26)dp[i] += dp[i - 2] ;}return dp[n - 1];}
};

这篇关于算法沉淀 —— 动态规划篇(斐波那契数列模型)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

基于Flask框架添加多个AI模型的API并进行交互

《基于Flask框架添加多个AI模型的API并进行交互》:本文主要介绍如何基于Flask框架开发AI模型API管理系统,允许用户添加、删除不同AI模型的API密钥,感兴趣的可以了解下... 目录1. 概述2. 后端代码说明2.1 依赖库导入2.2 应用初始化2.3 API 存储字典2.4 路由函数2.5 应

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...