【动态规划】斐波那契数列模型总结

server/2024/11/14 2:10:56/

一、第 N 个泰波那契数

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

题目描述:

题目分析:

1、状态表示:

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

2、状态转移方程:

由题意可知第 i 个数等于其前三个数之和

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

3、初始化:

由于递推公式中存在 i-1、i-2、i-3,当 i=0、1、2的时候,就会出现-1,-2,-3这种非法的下标值,导致数组访问异常。因此,我们需要在填表前将 0,1,2 位置的值初始化。题目中也直接告诉了我们这些位置的初始值:

dp[0]=0 、 dp[1]=1 、 dp[2]=1

4、优化

其实每次在求取 dp[i] 的时候,只需要知道其前三个元素的值即可。也就是说我们在每次更新后只需要保存最后的三个数即可。通过三个数的值就能更新出下一个 dp 值。

代码实现:

java">class Solution {public int tribonacci(int n) {int[] dp=new int[]{0,1,1};if(n==0)return 0;if(n<3)return 1;for(int i=3;i<=n;i++){dp[i%3]=dp[0]+dp[1]+dp[2];}return dp[n%3];}
}

二、三步问题

题目链接: 三步问题

题目描述:

题目分析:

1、状态表示:

dp[i] 表⽰:到达 i 位置时,⼀共有多少种⽅法。

2、状态转移方程:

到达第 i 级台阶的所有方法我们不好确定,但我们可以确定到达第 i 级台阶的上一步只有三种可能:

  • 从 i-1置上一级台阶,且到达 i-1 位置的方法数为 dp[i-1]
  • 从 i-2置上二级台阶,且到达 i-2 位置的方法数为 dp[i-2]
  • 从 i-3置上三级台阶,且到达 i-3 位置的方法数为 dp[i-3]

而到达第 i 级台阶的方法数就应该为其所有上一步的方式之和:

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

注意:由于这里计算的结果可能会很大。因此我们需要对结果进行取模。并且为了防止求和时溢出,在每次求和时都要先取模再求和

3、初始化:

由于递推公式中存在 i-1、i-2、i-3,当 i=0、1、2的时候,就会出现-1,-2,-3这种非法的下标值,导致数组访问异常。因此,我们需要在填表前将 0,1,2 位置的值初始化。由题意很容易就能求出这些位置的初始值:

dp[0]=1 、 dp[1]=2 、 dp[2]=4

代码实现:

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

三、 使用最小花费爬楼梯

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

题目描述:

题目分析:

1、状态表示:

dp[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] 

我们每次只需要取两种情况的最小值即可。

因此:dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3、初始化:

很明显 i=0 或 i=1时是无法使用递推公式的。因此我们需要先把他们给初始化了。

由题意可得 dp[0] = dp[1] = 0 ,因为可以直接选择从第0级或第1级台阶开始爬楼梯,不需要任何花费

代码实现:

java">class Solution {public int minCostClimbingStairs(int[] cost) {int n=cost.length;int[] dp=new int[n+1];for(int i=2;i<=n;i++){dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];}
}

四、解码方法

题目链接: 解码方法

题目描述:

题目分析:

1、状态表示:

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

2、状态转移方程:

关于 i 位置的编码状况,我们可以分为下⾯两种情况:
  • i 位置上的数单独解码成⼀个字⺟;
  • i 位置上的数与 i - 1 位置上的数结合,解码成⼀个字⺟。
下⾯我们就上⾯的两种解码情况,继续分析:
让 i 位置上的数单独解码成⼀个字⺟,就存在两种情况:
  • 解码成功:i 位置上的数在 [1, 9] 之间的时候,说明 i 位置上的数是可以单独解码的,那么此时 [0, i] 区间上的解码⽅法应该等于 [0, i - 1] 区间上的解码⽅法。因为 [0, i - 1] 区间上的所有解码结果,后⾯填上⼀个 i 位置解码后的字⺟就可以了。此时 dp[i] = dp[i - 1]
  • 解码失败:i 位置上的数是 0 的时候,说明 i 位置上的数是不能单独解码的,那么此时 [0, i] 区间上不存在解码⽅法。因为 i 位置如果单独参与解码,但是解码失败了,那么前⾯做的努⼒就全部⽩费了。此时 dp[i] = 0
让 i 位置上的数与 i - 1 位置上的数结合在⼀起,解码成⼀个字⺟,也存在两种情况:
  • 解码成功:当结合的数在 [10, 26] 之间的时候,说明 [i - 1, i] 两个位置是可以解码成功的,那么此时 [0, i] 区间上的解码⽅法应该等于 [0, i - 2 ] 区间上的解码⽅法,原因同上。此时 dp[i] = dp[i - 2] 
  • 解码失败:当结合的数在 [0, 9] [27 , 99] 之间的时候,说明两个位置结合后解码失败(这⾥⼀定要注意 00 01 02 03 04 ...... 这⼏种情况),那么此时 [0, i] 区间上的解码⽅法就不存在了,原因依旧同上。此时 dp[i] = 0
综上所述: dp[i] 最终的结果应该是上⾯四种情况下,解码成功的两种的累加和,因此可以得到状态转移⽅程
  • s[i] 上的数在 [1, 9] 区间上时: dp[i] += dp[i - 1] 
  • s[i - 1] s[i] 上的数结合后,在 [10, 26] 之间的时候: dp[i] += dp[i - 2] 
  • 如果上述两个判断都不成⽴,说明没有解码⽅法, dp[i] 就是默认值 0

3、初始化:

可以在最前⾯加上⼀个辅助结点,帮助我们初始化。这时 dp[i] 就表示 [0 i] 区间上的编码数。这里当前两个数能成功解码时,dp[2]就应该要加上 dp[0] 的值,因此我们需要让 dp[0] 初始化为 1。 

代码实现:

java">class Solution {public int numDecodings(String s) {char[] cs=s.toCharArray();int n=s.length();if(cs[0]-'0'==0)return 0;int[] dp=new int[n+1];dp[1]=1;dp[0]=1;for(int i=2;i<=n;i++){if(cs[i-1]-'0'!=0)dp[i]=dp[i-1];if(cs[i-2]-'0'==0)continue;int x=(cs[i-2]-'0')*10+cs[i-1]-'0';if(x<=26){dp[i]+=dp[i-2];}}return dp[n];}
}


那么本篇文章就到此为止了,如果觉得这篇文章对你有帮助的话,可以点一下关注和点赞来支持作者哦。如果有什么讲的不对的地方欢迎在评论区指出,希望能够和你们一起进步✊


http://www.ppmy.cn/server/141335.html

相关文章

15分钟学 Go 第 49 天 :复杂项目开发

第49天&#xff1a;复杂项目开发 欢迎来到第49天的Go语言学习&#xff01;今天&#xff0c;我们将深入探讨如何开始一个中型项目。这将包括项目的设计、架构、代码实现和运行。我们将以开发一个简单的任务管理系统为例。 1. 项目概述 我们的目标是构建一个基本的任务管理系统…

工单系统在手,双重挑战无忧

工单管理系统解决效率低下、进度追踪难、资源分配不合理等问题&#xff0c;提升客户满意度和合规性。ZohoDesk等功能助企业自动化处理服务请求&#xff0c;优化资源配置&#xff0c;确保信息畅通&#xff0c;简化合规审计。 什么是工单管理系统&#xff1f; 工单管理系统&…

C++ 链表的实现

为了动态和灵活地增加、删除数据&#xff0c;可以通过指针动态地管理元素。链表的每个元素成为一个节点&#xff0c;每个节点的结构内都包含一个指向下一个节点的指针。通过这些节点的指针&#xff0c;最终可以将这些节点元素链接在一起&#xff0c;因此这种数据形式称为链表。…

MATLAB和Python多语高维转录分析

MATLAB高维转录分析代码片段 在 MATLAB 中进行高维转录分析&#xff08;例如单细胞 RNA 测序 scRNA-seq 分析&#xff09;可以使用以下步骤&#xff0c;包括数据导入、预处理、降维、聚类和差异表达分析。 MATLAB 的矩阵操作能力和工具箱&#xff08;如统计和机器学习工具箱&a…

华为云创建ECS前台展示规格类型选项是怎么做到的?

前台展示很多规格可选&#xff0c;怎么做到的&#xff1f;先了解规格其实都是管理员在后台service_OM创建好规格 1.规格 1.1设置自定义标签打通规格和主机组还能体验调度功能 引申&#xff1a;AZ可用分区&#xff08;为了做容灾&#xff09; 为什么在界面可以让我√az0.dc0,…

ssm090校园活动管理平台+vue(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;校园活动管理平台设计与实现 摘 要 使用旧方法对校园活动信息进行系统化管理已经不再让人们信赖了&#xff0c;把现在的网络信息技术运用在校园活动信息的管理上面可以解决许多信息管理上面的难题&#xff0c;比如处…

HTML 鼠标滑动 页面的header背景从透明色变为黑色

要实现当鼠标滑动时&#xff0c;页面的header背景从透明色变为黑色&#xff0c;你可以使用JavaScript来监听滚动事件&#xff0c;并根据页面的滚动位置来改变header的背景颜色。 <!DOCTYPE html> <html lang"en"> <head> <meta charset"U…

大顶堆的基本操作

目录 堆的基本操作 //堆排序 堆的基本操作 ​​​​​ * 1.找到最后一个非叶子节点 * 2.从后向前遍历&#xff0c;对每个节点执行下潜操作 删除堆顶元素 * 1.将堆顶元素与最后一个元素交换位置 * 2.将最后一个元素删除 * 3.然后从上向下调整堆 public class MaxHeap {int …