LeetCode刷题---斐波那契数列模型

news/2024/4/17 17:10:31

顾得泉:个人主页

个人专栏:《Linux操作系统》  《C/C++》  《LeedCode刷题》

键盘敲烂,年薪百万!


一、第N个泰波那契数

题目链接:1137. 第 N 个泰波那契数  

题目描述

泰波那契序列Tn定义如下:

        T0=0,T1=1,T2= 1,且在n>=0的条件下Tn+3= Tn+Tn+1t+Tn+2

        给你整数n,请返回第n个泰波那契数Tn的值。

示例1:

        输入:n=4

        输出:4

解释:

        T_3=0+1+1=2

        T_4=1+1+2=4

示例2:

        输入:n= 25

        输出:1389537

解法

1.状态表示:

        这道题可以「根据题目的要求」直接定义出状态表示:

        dp[i]表示:第i个泰波那契数的值。

2.状态转移方程:

        题目已经非常贴心的告诉我们了∶

             dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

3.初始化:

        从我们的递推公式可以看出,dp[i]在i = 0以及i = 1的时候是没有办法进行推导的,因为dp[-2]或dp[-1]不是一个有效的数据

        因此我们需要在填表之前,将0,1,2位置的值初始化

        题目中已经告诉我们dp[0] = 0,dp[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;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];}
};

优化解法

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;}
};

二、三步问题

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

题目描述

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

示例1:

        输入:n=3

        输出:4

说明:有四种走法

示例2:

        输入:n=5

        输出:13

提示:

        n范围在[1,1000000]之间

解法

​1.状态表示

       这道题可以根据「经验+题目要求」直接定义出状态表示:dp[i]表示:到达i位置时,一共有多少种方法。

2.状态转移方程

       以i位置状态的最近的一步,来分情况讨论:

       如果dp[i]表示小孩上第1阶楼梯的所有方式,那么它应该等于所有上关步的方式之和:

             i. 上一步上一级台阶,dp[i] += dp[i - 1] 

             ii.上一步上两级台阶,dp[i] += dp[i - 2]

             iii.上一步上三级台阶,dp[i] += dp[i - 3]

       综上所述,dp[i] = dp[i - 1]+ dp[i - 2] +dp[i]

       需要注意的是,这道题目说,由于结果可能很大,需要对结果取模。

       在计算的时候,三个值全部加起来再取模,即(dp[i l+ dp[i - 2] + dp[i - 3])% MOD是不可取的,大家可以试验一下,取题目范围内最大值时,网站会报错signedinteger overflow。对于这类需要取模的问题,我们每计算一次(两个数相加/乘等),都需要取一次模。否则,万一发生了溢出,我们的答案就错了。

3.初始化

       从我们的递推公式可以看出,dp[i]在i = 0, i = 1以及i = 2的时候是没有办法进行推导的,因为dpL3]dp[-2]或dp[-1]不是一个有效的数据

       因此我们需要在填表之前,将1,2,3位置的值初始化

       根据题意,dp[1= 1, dp[2] = 2,dp[3] = 4

4.填表顺序

        毫无疑问是「从左往右」

5. 返回值

       返回dp[n]的值

代码实现

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

优化解法

class Solution {
public:int waysToStep(int n) {const int MOD = 1e9 + 7;if(n == 1 || n == 2) return n;if(n == 3) return 4;int a = 1, b = 2, c = 4, d = 0;for(int i = 4;i <= n; i++){   d = ((a + b) % MOD + c) % MOD;a = b;b = c;c = d;}return d;}
};

三、使用最小花费爬楼梯

题目链接:​ 746. 使用最小花费爬楼梯  

题目描述

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

       你可以选择从下标为0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

示例1:

        输入: cost = [10,15,20]

        输出:15

解释:

       你将从下标为1的台阶开始

       支付15,向上爬两个台阶,到达楼梯顶部,总花费为15

示例2:

        输入: cost =[1,100,1,1,1,100,1,1,100,1]

        输出:6

解释:

        你将从下标为0的台阶开始。

        支付1,向上爬两个台阶,到达下标为2的台阶。

        支付1,向上爬两个台阶,到达下标为4的合阶。

        支付1,向上爬两个台阶,到达下标为的合阶。

        支付1,向上爬一个台阶,到达下标为7的台阶。

        支付1,向上爬两个台阶,到达下标为9的台阶。

        支付1,向上爬一个合阶,到达楼梯顶部。

        总花费为6。

注意注意:

     在这道题中,数组内的每一个下标[o,n - 1]表示的都是楼层,而顶楼的位置其实是在n的位置! 

解法

​1.状态表示:

       这道题可以根据「经验+题目要求」直接定义出状态表示:

       以1位置为结尾,巴拉巴拉

       dp[i]表示:到达1位置时的最小花费。(注意:到达i位置的时候,i位置的钱不需要算上)

2.状态转移方程:

根据最近的一步,分情况讨论:

             先到达i - 1的位置,然后支付cost[i - 1]

             接下来走一步走到i位置:dp[i - 1]+ csot[i - 1] ;

             先到达i -2的位置,然后支付cost[i - 2]

             接下来走一步走到i位置:dp[i - 2]+ csot[i - 2]。

3.初始化:

       从我们的递推公式可以看出,我们需要先初始化i = 0,以及 i 1位置的值。容易得到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);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 位 的整数。

示例 1:

输入:s = "12"
输出:2
解释:它可以解码为"AB"(1 2)或者 "L"(12)。

示例 2:

输入:s = "226"
输出:3
解释:它可以解码为"BZ"(2 26),"VF"(22 6), 或者"BBF"(2 2 6) 。

示例 3:

输入:s = "06"
输出:0
解释:"06" 无法映射到"F",因为存在前导零("6" 和 "06" 并不等价)。

提示:

  • 1 <= s.length <= 100
  • s 只包含数字,并且可能包含前导零。

解法

​类似于斐波那契数列~

1.状态表示:

       根据以往的经验,对于大多数线性dp,我们经验上都是下以某个位置结束或者开始做文章,这里我们继续尝试「用i位置为结尾」结合「题目要求」来定义状态表示。

        dp[i]表示:字符串中[0,i]区间上,共有多少种编码方法。

2.状态转移方程:

        定义好状态表示,我们就可以分析i位置的dp值,如何由「前面」或者「后面」的信息推导出
来。关于i位置的编码状况,我们可以分为下面两种情况:

             i. 让i位置上的数单独解码成一个字母;

             ii.让i位置上的数与i - 1位置上的数结合,解码成一个字母。

下面我们就上面的两种解码情况,继续分析:

     让i位置上的数单独解码成一个字母,就存在「解码成功」和「解码失败」两种情况:

          i.解码成功:当i位置上的数在[1,9]之间的时候,说明1位置上的数是可以单独解码的,那么此时[0,i]区间上的解码方法应该等于[0, i - 1]区间上的解码方法。因为[0,i - 1]区间上的所有解码结果,后面填上一个 i位置解码后的字母就可以了。此时dp[i] = dp[i - 1] ;

          ii.解码失败:当i位置上的数是 0的时候,说明1位置上的数是不能单独解码的,那么此时[0,i]区间上不存在解码方法。因为1位置如果单独参与解码,但是解码失败了,那么前面做的努力就全部白费了。此时dp[i] = 0。

     让1位置上的数与i – 1位置上的数结合在一起,解码成一个字母,也存在「解码成功」和「解码失败」两种情况:

          i.解码成功:当结合的数在[10,26]之间的时候,说明([i - 1,i]两个位置是可以解码成功的,那么此时[0,i]区间上的解码方法应该等于[0,i - 2]区间上的解码方法,原因同上。此时的dp[i] = dp[i - 2] ;
          ii.解码失败:当结合的数在[0,9]和[27 , 99]之间的时候,说明两个位置结合后解码失败(这里一定要注意00 01 02 03 04......这几种情况),那么此时[0,i]区间上的解码方法就不存在了,原因依旧同上。此时dp[i] = 0。

       综上所述: dp[i]最终的结果应该是上面四种情况下,解码成功的两种的累加和(因为我们关心的是解码方法,既然解码失败,就不用加入到最终结果中去),因此可以得到状态转移方程

       ( dp[i]默认初始化为0) 

          i. 当s[i]上的数在[1,9]区间上时: dp[il t= dp[i - 1]

          ii.当 s[i - 1]与s[i]上的数结合后,在[10,26之间的时候:dp[i] +=dp[i - 2] ;

       如果上述两个判断都不成立,说明没有解码方法,dp[i]就是默认值0。

3.初始化:

方法一(直接初始化)∶

     由于可能要用到i - 1以及个位置上的dp值,因此要先初始化「前两个位置」。初始化 dp[o]:

         i. 当s[0] == '0'时,没有编码方法,结果dp[0] = 0 ;

         ii.当s[0] != '0'时,能编码成功,dp[0] = 1

初始化 dp[1j:

         i. 当s[1在[1,9]之间时,能单独编码,此时dp[1] += dp[0](原因同上,dp[1]默认为0)

         ii.当 s[0]与s[1]结合后的数在([10,26]之间时,说明在前两个字符中,又有一种编码方式,此时dp[1] += 1

方法二(添加辅助位置初始化)∶

     可以在最前面加上一个辅助结点,帮助我们初始化。使用这种技巧要注意两个点:

         i.辅助结点里面的值要保证后续填表是正确的;

         ii.下标的映射关系

4.填表顺序:

       毫无疑问是「从左往右」

5.返回值:

       应该返回dp[n - 1]的值,表示在[o,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 t = (s[0] - '0') * 10 + s[1] - '0';if(t >= 10 && 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(t >= 10 && t <= 26) dp[i] += dp[i-2];}return dp[n-1];}
};

代码实现---方法二

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];int t = (s[i-2] - '0') * 10 + s[i-1] - '0';if(t >= 10 && t <= 26) dp[i] += dp[i-2];}return dp[n];}
};

结语:今日的刷题分享到这里就结束了,希望本篇文章的分享会对大家的学习带来些许帮助,如果大家有什么问题,欢迎大家在评论区留言~~~ 


https://www.xjx100.cn/news/3119080.html

相关文章

C# WPF上位机开发(倒计时软件)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 生活当中&#xff0c;我们经常会遇到倒计时的场景&#xff0c;比如体育运动的时候、考试的时候等等。正好最近我们学习了c# wpf开发&#xff0c;完…

Linux常用命令——badblocks命令

在线Linux命令查询工具 badblocks 查找磁盘中损坏的区块 补充说明 badblock命令用于查找磁盘中损坏的区块。 硬盘是一个损耗设备&#xff0c;当使用一段时间后可能会出现坏道等物理故障。电脑硬盘出现坏道后&#xff0c;如果不及时更换或进行技术处理&#xff0c;坏道就会越…

【数据挖掘】国科大刘莹老师数据挖掘课程作业 —— 第二次作业

Written Part 1. 给定包含属性&#xff5b;Height, Hair, Eye&#xff5d;和两个类别&#xff5b;C1, C2&#xff5d;的数据集。构建基于信息增益&#xff08;info gain&#xff09;的决策树。 HeightHairEyeClass1TallBlondBrownC12TallDarkBlueC13TallDarkBrownC14ShortDark…

TypeScript 5.3

导入属性 TypeScript 5.3支持导入属性提案的最新更新。 导入属性的一个用例是向运行库提供有关模块预期格式的信息。 // We only want this to be interpreted as JSON, // not a runnable/malicious JavaScript file with a .json extension. import obj from "./somet…

安网AC智能路由系统actpt_5g.data敏感信息泄露漏洞复现 [附POC]

文章目录 安网AC智能路由系统actpt_5g.data敏感信息泄露漏洞复现 [附POC]0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 安网AC智能路由系统actpt_5g.data敏感信息泄露漏洞复现 [附POC] 0x01 前言 免责声明&#xff1a;请勿利…

外汇天眼:外汇市场中的“双向交易”是什么意思?

说到外汇市场&#xff0c;总免不了提到它双向交易的优势&#xff0c;很多新手会对这一点有所疑问&#xff0c;今天我们就帮大家解决这一个疑问。 何谓双向交易&#xff1f; 金融市场上&#xff0c;交易者最常接触到的股票&#xff0c;多属于单向交易。 单向交易的模式便是「先…

性能分析之tcpdump抓包

1. 简单用法 tcpdump -i any port 8382 -s 0 -C 200 -w steem.cap 1.1. 参数说明 -i any 指定抓取的网卡&#xff0c;通常是eth0&#xff0c;示例里any表示抓取所有网卡的包;&#xff1b; port 8382 指定抓取的端口&#xff0c;包括发送端口或接收端口&#xff0c…

四则计算机实现(C++)(堆栈的应用)

算法要求&#xff1a; 输入一个数学表达式(假定表达式输入格式合法)&#xff0c;计算表达式结果并输出。数学表达式由单个数字和运算符“”、“-”、“*”、“/”、“(、) ”构成&#xff0c;例如 2 3 * ( 4 5 ) - 6 / 4。变量、输出采用整数&#xff0c;只舍不入。 图解算…