动态规划：斐波那契数列模型

c_773018494

251人浏览 · 2026-06-10 00:28:47

c_773018494 · 2026-06-10 00:28:47 发布

本文将通过以下三个板块解决问题：

1.题目解释

2.算法原理

3.代码编写

在算法原理部分，我将从5个方面讲解：

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

第 N 个泰波那契数（easy）

1.题目解析

对于动态规划算法，我们要从简单问题着手，逐渐加深理解。

在这个问题中，我们可以发现题目为我们提供了一个等式，通过示例不难看出n所对应的值是由n-1,n-2,n-3所对应的值相加得到的。

2.算法原理

2.1状态表示

在前期的学习中，将主要通过“经验+题目提供”的方式解决动态规划的问题。在前期学习动态规划算法时，一定要简单理解dp表，在逐渐深入的学习中理解dp表，不可贪心，dp表其实是一个复杂的存在。

dp表一般为一个一维数组或者二维数组。

这道题可以"根据题⽬的要求"直接定义出状态表⽰：

dp[i] 表⽰：第 i 个泰波那契数的值。

2.2状态转移方程

状态转移就是要通过之前状态或者之后状态，经过处理后得出当前状态，在题目中体现为所求状态dp[i-1],dp[i-2]......dp[0] 或者dp[i+1],dp[i+2].......dp[n]经过f操作后，得到dp[i]。

"根据题⽬的要求"直接定义出状态转移方程：

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

2.3初始化

根据状态转移方程，我们要访问dp[i]后面的三个值，而此时就可能出现“越界访问”问题。

2.4填表顺序

从左往右。

2.5返回值

返回dp[n]。

3.代码编写

动态规划问题的代码编写步骤较为固定

创建dp表
初始化
填表
返回值

class Solution {
public:
    int tribonacci(int n) {
        //动态规划解题
        vector<int> dp(n + 1);//动态规划表
        
        if(n == 0) return n;//处理边界问题
        if(n == 1 || n == 2) return 1;
        dp[0] = 0; dp[1] = 1; dp[2] = 1;
        
        for(int i = 3; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];//动态规划方程
        }
        return dp[n];
        
    }
};

三步问题（easy）

1.题目解析

根据我们的举例，发现当n>=4时满足等式d[n] = d[n-1] + d[n-2] + d[n-3]

题目中让我们%1000000007（1e9 + 7），这是因为最后结果可能大于INT_MAX，leetcode会报错

2.算法原理

2.1状态表示

2.2状态转移方程

2.3初始化

根据我们对题目的解析，当n>=4时，满足我们的状态转移方程，故我们只需要初始化下标为0，1，2，3这几个位置

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

2.4填表顺序

从左往右

2.5返回值

返回 dp[n]

3.代码编写

class Solution {
public:
    int waysToStep(int n) {
        vector<long int> dp(n + 1);
        if(n < 3) return n;//处理边界问题
        if(n == 3) return 4;
        dp[1] = 1; dp[2] = 2; dp[0] = 0;dp[3] = 4;
        for(int i = 4; i <= n; i++)
            dp[i] = ((dp[i-1] + dp[i-2]) % 1000000007 + dp[i-3]) % 1000000007;//动态规划方程
            
        return dp[n];
    }
};

3.使⽤最⼩花费爬楼梯（easy）

1.题目解析

2.算法原理

2.1状态表示

2.2状态转移方程

这道题相比前面的题在状态转移方程的推到方面更为复杂，这是动态规划算法最难的部分，这道题由于在执行每一步时都有“迈一步还是迈两步”两种可能，故而所推导出的状态转移方程也有两种

2.3初始化

根据题目，我们开始时可以选择从下标为0或者下标为1的位置开始，这是不需要任何花费的，而且dp表所存放的是到达这一阶梯的最小花费，所以dp[1] = 0; dp[0] = 0

2.4填表顺序

从左到右

2.5返回值

dp[n]

3.代码编写

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);//动态规划表，表示到达dp[n]为这时的花费
        dp[0] = 0; dp[1] = 0;
        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];
    }
};

解码⽅法（medium）

1.题目解析

2.算法原理

2.1状态表示

根据经验“以i位置为结尾，······”+题目“解码总数”：

得出状态表示“以i位置为结尾，解码方式的总数为······”。

因此，我们的dp表内部应填入输入的字符串中每个字符位置所对应的解码总数

2.2状态转移方程

2.3初始化

由于可能要⽤到 i - 1 以及 i - 2 位置上的 dp 值，因此要先初始化「前两个位置」。

初始化 dp[0] ：

i. 当 s[0] == '0' 时，没有编码⽅法，结果 dp[0] = 0 ；

ii. 当 s[0] != '0' 时，能编码成功， dp[0] = 1

初始化 dp[1] ：

i. 当 s[1] 在 [1，9] 之间时，能单独编码，此时 dp[1] += dp[0] （原因同上，dp[1] 默认为 0 ）

ii. 当 s[0] 与 s[1] 结合后的数在 [10, 26] 之间时，说明在前两个字符中，⼜有⼀种编码⽅式，

此时 dp[1] += 1

2.4填表顺序

从左往右

2.5 返回值

应该返回 dp[n - 1] 的值，表⽰在 [0, n - 1] 区间上的编码⽅法。

3.代码编写

class Solution
{
 public:
     int numDecodings(string s) 
     {
         int n = s.size();
         vector<int> dp(n); // 创建⼀个 dp表

         // 初始化前两个位置
         dp[0] = s[0] != '0';
         if(n == 1) return dp[0]; // 处理边界情况

         if(s[1] <= '9' && s[1] >= '1') dp[1] += dp[0];
         int t = (s[0] - '0') * 10 + s[1] - '0';
         if(t >= 10 && t <= 26) dp[1] += 1;

     // 填表
         for(int i = 2; i < n; i++)
         {
             // 如果单独编码
             if(s[i] <= '9' && s[i] >= '1') dp[i] += dp[i - 1];
             // 如果和前⾯的⼀个数联合起来编码
             int t = (s[i - 1] - '0') * 10 + s[i] - '0';
             if(t >= 10 && t <= 26) dp[i] += dp[i - 2];
         }

     // 返回结果
     return dp[n - 1];
     }
 };