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

2401_87750511

382人浏览 · 2026-04-28 13:02:53

2401_87750511 · 2026-04-28 13:02:53 发布

动态规划

1、第 N 个泰波那契数
2、三步问题
3、最小花费爬楼梯
4、解码方法

1、第 N 个泰波那契数

第 N 个泰波那契数

在这里插入图片描述

1.1、题目理解

第 N 个泰波那契数，就是前三个泰波那契数求和。

1.2、原理分析

我们借助这道题，来入门动态规划的一般流程。

状态表示

创建一个一维（或二维）数组dp，数组中每一位上的值的含义，就是当前动态规划的状态表示。

状态表示怎么来的：

题目要求
题目要求 + 经验
分析问题的过程中，发现重复的子问题

这道题中，我们可以创建一维数组dp[n]。由于泰波那契数存在第0数，那么我们就可以直接利用一维数组dp[n]，当前的状态表示（数组第i位上的数）是第i个泰波那契数。

状态转移方程

也就是dp[i]，或者dp[i][j]等于什么。

本题中，
$d p [i] = d p [i - 1] + d p [i - 2] + d p [i - 3]$

初始化

初始化的目的是：保证填表时不越界。

这道题中，我们可不能利用状态转移方程计算dp[0], dp[1], dp[2]，因为数组下标会出现负值。

所以我们要提前设置好dp[0], dp[1], dp[2]。

填表顺序

填表顺序的目的是：保证填写当前状态时，所需要的状态已经提前准备好（填写好）。

我们要知道dp[i]，就要知道dp[i-1], dp[i-2], dp[i-3]；而要知道dp[i-1]，就要知道dp[i-2], dp[i-3], dp[i-4]……

所以当前的填表顺序，可以是从前向后。

返回值

返回题目所需的值。

1.3、代码演示

class Solution {
public:
    int tribonacci(int n) {
        //边界情况另外处理，防止越界
        //这里的边界情况需要先处理，再用通法
        if (n == 0) return 0;
        else if (n == 1 || n == 2) return 1;

        vector<int> dp(n+1, 0);
        dp[0] = 0;
        dp[1] = 1;//这里不特殊处理就会越界
        dp[2] = 1;

        for (int i = 3; i < n + 1; ++i)
        {//这里不特殊处理就会越界
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }
};

1.4、空间优化

我们通过分析，不难得出：要计算出第n个泰波那契数，只需要知道n-1, n-2, n-3泰波那契数。

我们设a, b, c, d，一开始a指向T[0]，b指向T[1]，c指向T[2]，d存计算的第n个泰波那契数：

在这里插入图片描述

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        else if (n == 1 || n == 2) return 1;
        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;
    }
};

我们可以看到，此时空间复杂度由O(N)降到了O(1)，实现了优化。

2、三步问题

三步问题

在这里插入图片描述

3.1、题目理解

首先我们要理解，我们算的是上台阶的方法数，不是上台阶的步数。

我们取前几个台阶分析：

在这里插入图片描述
跳到台阶1，有一种方法：

在这里插入图片描述
跳到台阶2，有两种方法：

从台阶1跳一阶
从地面跳两阶

在这里插入图片描述

跳到台阶3：

地面直接跳三阶
台阶1跳两阶
台阶2跳1阶

在这里插入图片描述
跳到台阶4，列举一遍，就能想到有7种方法。再结合题目样例的跳到台阶5有13种方法，我们就有感觉了：很像泰波那契序列。

3.2、原理分析

状态表示

设数组dp，dp[i]的含义是：跳到第i个台阶的方法数。

状态转移方程

跳到第i个台阶，只有三种情况：

最后从第i-1个台阶跳过来
最后从第i-2个台阶跳过来
最后从第i-3个台阶跳过来

有多少个跳到第i-1个台阶的方法数，即dp[i-1]等于多少，就有多少个最后从第i-1个台阶跳到第i个台阶的方法数。

同理，
有多少个跳到第i-2个台阶的方法数，即dp[i-2]等于多少，就有多少个最后从第i-2个台阶跳到第i个台阶的方法数。
有多少个跳到第i-3个台阶的方法数，即dp[i-3]等于多少，就有多少个最后从第i-3个台阶跳到第i个台阶的方法数。

所以，
$d p [i] = d p [i - 1] + d p [i - 2] + d p [i - 3]$

初始化

为了防止越界，我们设置：

dp[0]没有意义
dp[1] = 1
dp[2] = 2
dp[3] = 4

填表顺序

填表顺序很明显是从左往右

返回值

返回dp[i]。

3.3、代码演示

class Solution {
public:
    int waysToStep(int n) {
        if (n == 1 || n == 2) return n;
        else if (n == 3) return 4;

        const int 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];
    }
};

空间优化：

class Solution {
public:
    int waysToStep(int n) {
        if (n == 1) return 1;
        else if (n == 2) return 2;
        else if (n == 3) return 4;

        const int MOD = 1e9 + 7;

        int a = 1, b = 2, c = 4, d = 0;
        for (int i = 4; i <= n; ++i)
        {
            d = ((a + b) % MOD + c) % MOD;
            a = b; b = c; c = d;
        }

        return d;
    }
};

3、最小花费爬楼梯

使用最小花费爬楼梯

在这里插入图片描述

3.1、题目理解

可以从题干提取的信息：

给出整数数组cost，cost[i]是从第i层向上爬所需支付的费用。
可以向上跳1，或2层
可以规定起始位置为0下标，或1下标。

对于示例1，由于我们可以规定起始位置为0下标，或1下标。当规定0下标，最小花费为25（0—>1—>3）；当规定1下标，最小花费为15（1—>3），故总花费为15。

对于示例2，走法为：0—>2—>3—>4—>6—>7—>9—>10

3.2、原理分析及代码演示

依旧按五段式分析：状态表示、状态转移方程、初始化、填表顺序、返回值。

这里我们提供两种分析方法：

3.2.1、到i位置为止

状态表示：

dp[i]表示到下标i位置为止所需的最小花费。

由于最终我们需要知道到下标n位置（n = cost.size()）所需的最小花费，所以我们创建dp数组需要开辟n+1个元素空间，而不是n个空间。

状态转移方程：

由于我们可以向上跳1，或2层，所以dp[i]的值可以由dp[i-1]和dp[i-2]得出：

在这里插入图片描述

dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);

初始化：

由于可以规定起始位置为0下标，或1下标，那么：

dp[0] = dp[1] = 0;

填表顺序：

填表顺序为下标从小到大。

返回值：

返回dp[n]。

代码演示：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n+1);

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

3.2.2、从i位置开始

状态表示：

dp[i]表示从下标i位置开始，到登顶所需的最小花费。

那么这时，我们就不需要多开一个元素空间了。

状态转移方程：

由于我们可以向上跳1，或2层，dp[i]的值可以由dp[i+1]和dp[i+2]得出：

在这里插入图片描述

dp[i] = min(dp[i+1]+cost[i], dp[i+2]+cost[i]);

初始化：

从n-1位置跳到n，最小花费是：cost[n-1]。

从n-2位置跳到n，最小花费是：cost[n-2]。

dp[n-1] = cost[n-1];
dp[n-1] = cost[n-1];

填表顺序：

填表顺序为下标从大到小。

返回值：

由于可以规定起始位置为0下标，或1下标，那么我们应该取两者的最小值：

return min(dp[0], dp[1]);

代码演示：

class Solution {
public:
    int minCostClimbingStairs(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]);
        }

        return min(dp[0], dp[1]);
    }
};

4、解码方法

解码方法

状态表示

dp[i]表示到下标i处为止，string串的解码方法数。

状态转移方程

对于dp[i]字符，如果我们知道了到下标i-1处为止，string串的解码方法数，即dp[i-1]。接下来每一种解码序列，只需与dp[i]解码后的序列结合。

对于dp[i-1]与dp[i]字符的结合数num，如果我们知道了到下标i-2处为止，string串的解码方法数，即dp[i-2]。接下来每一种解码序列，只需num解码后的序列结合。

但是，对于dp[i]字符，如果为字符0，就不能有效解码，解码方法数就为0；对于dp[i-1]与dp[i]字符的结合数num，如果num的范围不在[10, 26]，也不能有效解码，解码方法数也为0。

在这里插入图片描述

初始化

dp[0]的初始化：

如果dp[0] = ‘0’，那么方法数为0。由于创建vector数组时会自动初始化（0），所以我们不做处理。
如果dp[0] != ‘0’，方法数dp[0]就为1。

dp[1]的初始化：

对于dp[1]
- 如果dp[1] = ‘0’，那么方法数为0。
- 如果dp[1] != ‘0’，方法数dp[1]就为dp[0]。
对于s[0]与s[1]的组合num：
- 如果num在范围内，方法数加1。
- 如果num不在范围内，不处理。

填表顺序

下标从小到大。

返回值

返回dp[n-1]。

代码演示：

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n);// n个空间，全部初始化成0

        // dp[0]
        if (s[0] != '0') ++dp[0];
        if (n == 1) return dp[0];

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

        for (int i = 2; i < n ; ++i)
        {
            if (s[i] != '0') dp[i] += dp[i-1];
            int num = (s[i-1] - '0')*10 + (s[i] - '0');
            if (num >= 10 && num <= 26) dp[i] += dp[i-2];
        }

        return dp[n-1];
    }
};