斐波那契数列模型：在动态规划的丝绸之路上追寻斐波那契的足迹（下）

文章目录 引言一. 第n个泰波那契数1.1 题目链接： leetcode /problems/n-th-tribonacci-number/description/1.2 题目分析：1.3 思路讲解：1.4 代码实现： 二. 三步问题2.1 题目链接： leetcode /problems/three-steps-problem-lcci/description/2.2 题目分析：2.3 思路讲解：2.4 代码实现： 三. 使用最小花费爬楼梯3.1 题目链接： leetcode /problems/min-cost-climbing-stairs/description/3.2 题目分析：3.3 思路讲解：3.4 代码实现： 四. 解码方法4.1 题目链接： leetcode /problems/decode-ways/description/4.2 题目分析：4.3 思路讲解：4.4 代码实现： 小结

引言

上篇我们介绍了用动态规划解决斐波那契模型的相关代码，本篇我们将结合具体题目，进一步深化对于该算法的理解运用。

一. 第n个泰波那契数 1.1 题目链接： leetcode /problems/n-th-tribonacci-number/description/ 1.2 题目分析：

定义如下：

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

给定n，求Tn

1.3 思路讲解：

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] 的值。

1.4 代码实现： class Solution { public: int tribonacci(int n) { //处理特殊情况 if(n==0) return 0; if(n==1 ||n==2) return 1; vector<int> f(n+1); f[1]=f[2]=1; for(int i=3;i<=n;i++) { f[i]=f[i-3]+f[i-2]+f[i-1]; } return f[n]; } };

代码分析：

以上代码存在大量冗余计算，实际上每次计算f[n]只需要使用临近前3个的值，因此可以进行数组重排的方式进行优化。

优化代码如下：

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; int d; for(int i=3;i<=n;i++) { d=a+b+c;//前3个数相加 //更新 a=b; b=c; c=d; } return d; } }; 二. 三步问题 2.1 题目链接： leetcode /problems/three-steps-problem-lcci/description/ 2.2 题目分析： 共有n节台阶每次可以上1节，2节或3节台阶求共有多少种上楼方法如果结果很大，需要对结果取模 2.3 思路讲解：

首先枚举情况，观察规律。

n=1时，1种 n=2时，2种 n=3时，4种 n=4时，7种 n=5时，13种

以n=4时为例，将路程划分为0->x->4

0->1->4，0->1共有1种方法0->2->4，0->2共有2种方法0->3->4，0->3共有4种方法

因此总计有1+2+4=7种

状态方程为：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

余下思路与上题基本一致

2.4 代码实现： class Solution { public: int waysToStep(int n) { //处理特殊情况 if(n==1) return 1; if(n==2) return 2; if(n==3) return 4; vector<int> dp(n+1); const int mod=1e9+7; dp[1]=1,dp[2]=2,dp[3]=4; for(int i=4;i<=n;i++) { dp[i]=((dp[i-3]%mod+dp[i-2]%mod)%mod+dp[i-1]%mod)%mod; } return dp[n]; } }; 三. 使用最小花费爬楼梯 3.1 题目链接： leetcode /problems/min-cost-climbing-stairs/description/ 3.2 题目分析： 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。支付此费用，即可选择向上爬一个或者两个台阶。可以从下标为0或1开始爬到楼顶指的是cost[n]，而非cost[n-1]求取最小花费 3.3 思路讲解：

根据题目一时我们提供的思路，首先考虑构建状态方程

由于终点是在楼顶即结尾处，因此状态改变方向可设置为从左向右每次可选择爬1个或者2个，因此相邻点之间的到达方式有两种 dp[i-1] ->dp[i] 爬1节，花费为dp[i-1]+cost[i-1]dp[i-2] ->dp[i] 爬2节，花费为dp[i-2]+cost[i-2]其中dp[i]表示到达该位置所需要的花费

因此状态方程可表示为dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3.4 代码实现： 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]; } }; 四. 解码方法 4.1 题目链接： leetcode /problems/decode-ways/description/ 4.2 题目分析： 给你一个只含数字的 非空 字符串 s ，请计算并返回解码方法的总数 。如果没有合法的方式解码整个字符串，返回 0。可解码的数字只在区间1-26内，如果为06或60这种情况，则无法解码，直接返回0即可 4.3 思路讲解：

对于一个字符串s， 如果可以解码：

s中的每个数字都可以被解码，或通过两两组合的方式进行解码如果两种方式都不适用，则一定无法解码，直接返回0即可

首先考虑构建状态方程，遍历方向为从左到右，因此结尾在右侧。

dp[i]表示到该字符为止，存在的解码方法数如果s[i]可以单独解码，即1<=s[i]<=9，那么dp[i]+=dp[i-1]如果s[i[还可以和s[i-1]组合解码，例如1 3组合为13，那么dp[i]+=dp[i-2]如果两种方式都不适用，则一定无法解码，直接返回0即可 4.4 代码实现： 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';//初始化，同时注意dp与源字符串对应的时候下标减1 for(int i=2;i<=n;i++) { //先判断能否单独编码 if(s[i-1]>='1' && s[i-1]<='9') 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]; } };

代码分析：

与之前不同的是，在此处将dp[0]设置为了1，而之前都是默认值0这是因为在本题中dp[0]的值会对后续产生影响，因为如果可以组合编码，那么dp[2]的值会因为dp[0]的值而改变，后续的dp值也会被依次影响,如果可以组合编码，那么此时dp[2]+=dp[0]时，方法应该加1，因此需要把dp[0]设置为1 小结

本篇关于动态规划解决斐波那契模型的讲解就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！