动态规划在斐波那契数列中的应用与优化
文章目录
前言
斐波那契数列是数学领域中一个经典的问题，在计算机科学中也有广泛的应用。从简单的递归算法到优化的动态规划方法，斐波那契数列的求解体现了算法设计和性能优化的精髓。本文将以动态规划为核心，系统地探讨如何高效地计算斐波那契数列，分析不同方法的时间与空间复杂度，并展示动态规划的强大之处。希望通过本研究，为算法设计爱好者提供启发，并在实际问题中应用该技术。
🌞一、1137. 第 N 个泰波那契数
题目链接：https://leetcode.cn/problems/n-th-tribonacci-number/description/
🌜1. 题目解析
Tribonacci 数列是一个递归数列，类似于斐波那契数列，但它的递推公式是：
- 递推公式：
T(n) = T(n-1) + T(n-2) + T(n-3)，对于n >= 3； - 初始条件：
T(0) = 0T(1) = 1T(2) = 1
需要实现一个函数 tribonacci(int n)，返回第 n 个 Tribonacci 数。
🌜2. 讲解算法原理
状态表示
设 dp[i] 表示第 i 个 Tribonacci 数，即前 i 个数的第三阶斐波那契数列。换句话说，dp[i] 是定义如下的递推关系：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，对于i >= 3。
状态转移方程
根据题目描述，Tribonacci 数列满足：
dp[0] = 0dp[1] = 1dp[2] = 1dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，对于i >= 3
初始化
初始化初始条件，保证在填写表格的时候不会越界：
dp[0] = 0dp[1] = 1dp[2] = 1
填表顺序
从 i = 3 开始递推填表，因为计算 dp[i] 时，需要依赖 dp[i-1], dp[i-2], 和 dp[i-3] 的值，这些值在计算当前状态时必须已知。因此：
- 填写顺序是从
i = 3开始递增。
返回值
最后返回 dp[n]，即第 n 个 Tribonacci 数。
🌜3. 编写代码
classSolution{public:inttribonacci(int n){// 3. 初始化（初始条件）if(n ==0)return0;if(n ==1|| n ==2)return1;// 1. 状态表示：dp[i] 表示第 i 个 Tribonacci 数 vector<int>dp(n +1); dp[0]=0, dp[1]= dp[2]=1;// 4. 填表顺序：从 i = 3 到 nfor(int i =3; i <= n; i++){// 2. 状态转移方程 dp[i]= dp[i-1]+ dp[i-2]+ dp[i-3];}// 5. 返回值：第 n 个 Tribonacci 数return dp[n];}};🌜4. 空间优化
classSolution{public:inttribonacci(int n){if(n ==0)return0;if(n ==1|| n ==2)return1;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;// 返回第 n 项};- 状态转移方程：
T(n) = T(n-1) + T(n-2) + T(n-3)。- 每次计算当前值
T(n)只需要T(n-1)、T(n-2)和T(n-3)。
- 滚动更新变量：
- 变量
a、b、c分别存储T(n-3)、T(n-2)和T(n-1)。
- 变量
- 减少空间复杂度：
- 原本需要一个大小为
n的数组来存储所有状态。 - 滚动数组通过动态更新变量，将空间复杂度从 O(n) 优化为 O(1)。
- 原本需要一个大小为
每次计算 d = a + b + c 后，将 a、b、c 滚动更新为下一轮所需的值：
a = b;// T(n-2) 成为 T(n-3) b = c;// T(n-1) 成为 T(n-2) c = d;// T(n) 成为 T(n-1)🌞二、面试题 08.01. 三步问题
题目链接：https://leetcode.cn/problems/three-steps-problem-lcci/
🌜1. 题目解析
这道题的目标是计算可以通过步数 1、2 和 3 从 0 到达台阶 n 的所有不同方法的总数。
每次可以选择迈 1 步、2 步或 3 步，并且答案需要对 1 0 9 + 7 10^9 + 7 109+7 取模。
🌜2. 讲解算法原理
状态表示
定义一个数组 dp[i]，表示到达第 i 个台阶的方法总数。
dp[i]包括从i−1、i−2、或i−3的台阶迈一步到达的所有方案数。
状态转移方程
状态转移公式为：
d p [ i ] = ( d p [ i − 1 ] + d p [ i − 2 ] + d p [ i − 3 ] ) % M O D dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) \% MOD dp[i]=(dp[i−1]+dp[i−2]+dp[i−3])%MOD
这里的取模操作是为了防止结果过大，确保结果保持在 1 0 9 + 7 10^9 + 7 109+7 的范围内。
初始化
根据题目条件：
- 如果 n = 1，只有 1 种方法，初始化
dp[1] = 1； - 如果 n = 2，有 2 种方法，初始化
dp[2] = 2； - 如果 n = 3，有 4 种方法，初始化
dp[3] = 4。
填表顺序
从小到大依次计算 dp[4] 到 dp[n]，通过累加前 3 项得到结果。
返回值
最终返回 dp[n] 即可。
🌜3. 编写代码
classSolution{public:intwaysToStep(int n){if(n ==1|| n ==2)return n;if(n ==3)return4;constint MOD =1e9+7; 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];}};🌞三、746. 使用最小花费爬楼梯
题目链接：https://leetcode.cn/problems/min-cost-climbing-stairs/description/
🌜1. 题目解析
这道题的目标是计算从数组开头或第二个元素出发，到达数组末尾所需的最小花费。
每次可以迈 1 步或 2 步，花费由数组 cost 决定，其中每个位置的值代表站在对应台阶上的代价。
🌜2. 讲解算法原理
状态表示
定义一个数组 dp[i]：
dp[i]表示到达台阶i所需的最小花费。
状态转移方程
我们可以从前一层（i−1）或前两层（i−2）迈步到 i，取最小值作为最优解：
d p [ i ] = min ( d p [ i − 1 ] + c o s t [ i − 1 ] , d p [ i − 2 ] + c o s t [ i − 2 ] ) dp[i] = \min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])
初始化
因为可以从第 0 层或第 1 层开始：
dp[0] = 0：从起点出发，不需要额外代价。dp[1] = 0：从起点开始直接跳到第 1 层，也没有代价。
填表顺序
从小到大计算 dp[i]，直至 dp[n] ，其中 n 是楼梯台阶数。
返回值
最终返回 dp[n]，即为到达顶部所需的最小花费。
🌜3. 编写代码
1. 解法一：自底向上填表
classSolution{public:intminCostClimbingStairs(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];}};2. 解法二：从顶层反推
classSolution{public:intminCostClimbingStairs(vector<int>& cost){int n = cost.size(); vector<int>dp(n); dp[n -1]= cost[n -1]; dp[n -2]= cost[n -2];for(int i = n -3; i >=0; i--){ dp[i]=min(dp[i +1]+ cost[i], dp[i +2]+ cost[i]);}returnmin(dp[0], dp[1]);}};🌞四、91. 解码方法
题目链接：https://leetcode.cn/problems/decode-ways/description/
🌜1. 题目解析
本题要求解码一个只包含数字的字符串 s，其中每个数字代表字母表中的字母（1 对应 ‘A’，2 对应 ‘B’，…，26 对应 ‘Z’）。
我们的任务是计算出所有可能的解码方案的数量。
🌜2. 讲解算法原理
状态表示
定义一个数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符能够解码的方式总数。
状态转移方程
两个字符解码：
如果前两个字符组成的数值在 [10, 26] 范围内，那么它们可以合并解码成一个字母。例如，s[i-2] 和 s[i-1] 组合形成一个数，如果这个数在 [10, 26] 内，则可以由 dp[i-2] 转移：
int t =(s[i-2]-'0')*10+(s[i-1]-'0');if(t >=10&& t <=26) dp[i]+= dp[i-2];单个字符解码：
如果当前位置的字符 s[i-1] 是有效的（即不等于 ‘0’），它可以独立解码为一个字母。
因此，dp[i] 可以由 dp[i-1] 转移而来：
if(s[i-1]!='0') dp[i]+= dp[i-1];初始化
dp[0] = 1：表示空字符串有 1 种解码方法。
dp[1] = s[0] != '0'：如果第一个字符不为 ‘0’，则有 1 种解码方法，否则没有解码方法。
填表顺序
从 i = 2 开始填表，一直到 i = n，逐步计算每个 dp[i] 的值。
返回值
最终返回 dp[n]，即为整个字符串的解码方法数量。
🌜3. 编写代码
classSolution{public:intnumDecodings(string s){int n = s.size(); vector<int>dp(n +1); dp[0]=1;// 保证后面的填表是正确的 dp[1]= s[0]!='0';// 第一个字符不能是 '0'for(int i =2; i <= n; i++){// 如果当前字符不是 '0'，可以单独解码if(s[i -1]!='0') dp[i]+= dp[i -1];// 如果当前和前一个字符组成的数字在 10 到 26 之间，也可以解码int t =(s[i -2]-'0')*10+(s[i -1]-'0');if(t >=10&& t <=26) dp[i]+= dp[i -2];}return dp[n];}};结语
本文通过对斐波那契数列的动态规划求解方法的分析与优化，展现了动态规划在减少冗余计算、提升算法效率上的显著优势。相比于递归方法，动态规划在时间复杂度和空间复杂度上均有更优的表现，同时也更易扩展到其他问题。斐波那契数列作为算法入门的重要实例，其研究不仅有助于理解动态规划的基本原理，更能为解决更复杂的现实问题奠定基础。未来，动态规划仍将在算法设计领域发挥重要作用，我们也期待更多优化和创新的出现。
今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！
