动态规划在斐波那契数列中的应用与优化

文章目录

• 前言
  • 🌞一、1137. 第 N 个泰波那契数
    • 🌜1. 题目解析
    • 🌜2. 讲解算法原理
      • 状态表示
      • 状态转移方程
      • 初始化
      • 填表顺序
      • 返回值
    • 🌜3. 编写代码
    • 🌜4. 空间优化
  • 🌞二、面试题 08.01. 三步问题
    • 🌜1. 题目解析
    • 🌜2. 讲解算法原理
      • 状态表示
      • 状态转移方程
      • 初始化
      • 填表顺序
      • 返回值
    • 🌜3. 编写代码
  • 🌞三、746. 使用最小花费爬楼梯
    • 🌜1. 题目解析
    • 🌜2. 讲解算法原理
      • 状态表示
      • 状态转移方程
      • 初始化
      • 填表顺序
      • 返回值
    • 🌜3. 编写代码
  • 🌞四、91. 解码方法
    • 🌜1. 题目解析
    • 🌜2. 讲解算法原理
      • 状态表示
      • 状态转移方程
      • 初始化
      • 填表顺序
      • 返回值
    • 🌜3. 编写代码
• 结语

前言

斐波那契数列是数学领域中一个经典的问题，在计算机科学中也有广泛的应用。从简单的递归算法到优化的动态规划方法，斐波那契数列的求解体现了算法设计和性能优化的精髓。本文将以动态规划为核心，系统地探讨如何高效地计算斐波那契数列，分析不同方法的时间与空间复杂度，并展示动态规划的强大之处。希望通过本研究，为算法设计爱好者提供启发，并在实际问题中应用该技术。

🌞一、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) = 0
  • T(1) = 1
  • T(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] = 0
• dp[1] = 1
• dp[2] = 1
• dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，对于 i >= 3

初始化

初始化初始条件，保证在填写表格的时候不会越界：

• dp[0] = 0
• dp[1] = 1
• dp[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 项};

1. 状态转移方程：
   • T(n) = T(n-1) + T(n-2) + T(n-3)。
   • 每次计算当前值 T(n) 只需要 T(n-1)、T(n-2) 和 T(n-3)。
2. 滚动更新变量：
   • 变量 a、b、c 分别存储 T(n-3)、T(n-2) 和 T(n-1)。
3. 减少空间复杂度：
   • 原本需要一个大小为 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前进的动力！