微信二维码制作小程序_网站制作报价是否合法_网络营销的宏观环境_谷歌优化工具

引言

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

一. 第n个泰波那契数

1.1 题目链接：https://leetcode.cn/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 题目链接：https://leetcode.cn/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 题目链接：https://leetcode.cn/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 题目链接：https://leetcode.cn/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与源字符串对应的时候下标减1for(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

小结

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