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

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

前言

​ 我们将深入探讨解决斐波那契数列模型相关问题的解决方法。通过一系列精心挑选的例题，我们将展示如何运用DP的核心原则来解决各种编程挑战，从泰波那契数的计算到楼梯爬升问题，再到解码方法的多样性。每个问题都将通过状态表示、状态转移方程、初始化、填表顺序和返回值的详细分析来解构，旨在提供一个清晰的算法实现框架，帮助读者掌握DP的精髓，并在实际编程中灵活运用。

---

一、第 N 个泰波那契数

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

泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn + 3 = Tn + Tn + 1 + Tn + 2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

算法流程：

1. 状态表示

由题给出的要求：返回第 n 个泰波那契数 Tn 的值，所以确定 dp[i] 表示：第 i 个泰波那契数的值

2. 状态转移方程

对题中给出的递推公式：T_n+3 = T_n + T_n+1 + T_n+2，两边同时令n = n-3时，可得T_n = T_n-3 + T_n-2 + T_n-1，所以我们可以得到状态转移方程：

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

3. 初始化

由状态转移方程可知，数组下标不能小于0，故 i 的取值最小为 i = 3，所以我们在填表之前需要将 0,1,2 的位置值初始化。由题中给出 T₀， T₁， T₂ 的值，即可初始化：dp[0] = 0, dp[1] = dp[2] = 1

4. 填表顺序

从左往右

5. 返回值

要求T_n的值，应该返回 dp[n] 的值

示例代码：

int tribonacci(int n) 
{
    // 注意提前处理边界条件，避免访问越界
    if (n == 0) { return 0; }
    if (n == 1 || n == 2) { return 1; }

    // 滚动数组节约空间
    size_t a = 0, b = 1, c = 1;
    size_t result = a + b + c;
    for (int i = 3; i < n; ++i)
    {
        a = b;
        b = c;
        c = result;

        result = a + b + c;
    }

    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二、三步问题

题目链接：三步问题

有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。

实现一种方法，计算小孩有多少种上楼梯的方式。

结果可能很大，你需要对结果模1000000007。

提示:

​ n范围在[1, 1000000]之间

算法流程：

1. 状态表示

dp[i] 表示：到达 i 位置时，一共有多少种方法

2. 状态转移方程

由于 dp[i] 表示一共多少中方式可以到 i 位置，且题目规定一次可以上1,2,3个台阶，所以得到状态转移方程：

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

需要注意这里由于题目列出计算出结果的数据量可能过大，需要对结果的可能数作取模运算，所以尽量在三项中每两项相加后就进行一次取模运算，避免数据溢出。即为dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007

3. 初始化

从我们的状态转移方程可以看出，方程中 i 的取值最小为3，但是题目中给出的提示：n的取值大于等于1，所以 i 的最小取值应该为4，接着可以通过上面的递推公式陆续推导出其他下标位置的值。那么初始化：dp[1] = 1, dp[2] = 2, dp[3] = 4

4. 填表顺序

从左往右

5. 返回值

应该返回 dp[n] 的值

示例代码：

int waysToStep(int n) {
    // 递推公式 Tn = T<n-1> + T<n-2> + T<n-3>
    size_t a = 1, b = 2, c = 4;
    if (n == 1) { return a; }
    else if (n == 2) { return b; }
    else if (n == 3) { return c; }

    size_t result = 0;
    for (size_t i = 4; i <= n; i++)
    {
        result = ((a + b) % 1000000007 + c) % 1000000007;

        a = b;
        b = c;
        c = result;
    }

    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三、使用最小花费爬楼梯

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

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

注意：这里cost[n]对应的每个下标表示的都是楼层，而楼顶需要到达下标为n的位置，即一共 n+1 个位置。

算法流程：

1. 状态表示

dp[i] 表示：到达 i 位置时的最小花费。（注意：这里i可以取n，所以数组长应该设为n+1）

2. 状态转移方程

由题我们得知，每次跨越单位可以是1或2，所以 dp[i] 的值应该是一步前的位置对应的已花费金额+从一步前位置到该位置cost金额 与 两步前的位置对应的已花费金额+从两步前位置到该位置cost金额 相比的最小值

3. 初始化

从状态转移方程可以看出，我们需要初始化 i = 0 和 i = 1位置的值，由题：dp[0] = dp[1] = 0

4. 填表顺序

从左往右

5. 返回值

根据我们前面的推导，数组应该初始化长度为n+1，返回值为 dp[n]，而非 dp[n - 1]

示例代码：

int minCostClimbingStairs(vector<int>& cost) {
    size_t n = cost.size();
    vector<int> dp(n + 1, 0);
    // dp[i]表示到第i位置的最小花费
    // dp[i] = min(dp[i - 1]+cost[i - 1], dp[i - 2]+cost[i - 2])

    // 1.初始化
    dp[0] = dp[1] = 0;
    // 2.填表
    for (size_t i = 2; i <= n; i++)
    {
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }

    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四、解码方法

题目链接：解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
1
2
3
4

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)
• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

算法流程：

1. 状态表示

由于我们需要遍历整个字符串才能做出判断，那么不妨设定以 i 位置为结尾，一共有多少种解码方法，所以：dp[i] 表示：字符串中 [0, i] 区间一共有多少种解码方法

2. 状态转移方程

根据我们前面分析的 i 位置状态表示，我们在考虑 i 位置时已经将 i - 1 位置的数字纳入考虑范围，因为题中给出的解码条件可以单独解码，也可以和 i - 1 位置联合解码。所以我们不必在分析 i - 1 位置时考虑 (i - 1) + 1 位置的值是否可以与自身进行联合编码，这正是因为在分析 i 位置时自然会分析 i - 1 位置。

关于 i 位置的解码情况，可以分为单独解码和联合解码两种方式：

• **单独解码：**单独考虑 i 位置上的数可以解码为一个字母。
• **联合解码：**让 i 位置的数与 i - 1 位置的数结合，解码成一个字母。

<1> 让 i 位置上的数单独解码，存在解码成功与失败

1. 解码成功：当 i 位置上的数在 [1, 9] 之间的时候，说明 i 位置上的数是可以单独解码的，那么此时 [0, i] 区间上的解码方法应该等于 [0, i - 1] 区间上的解码方法。因为 [0, i - 1] 区间上的所有解码结果，后面填上一个 i 位置解码后的字母就可以了。此时 dp[i] = dp[i - 1]
2. 解码失败：当 i 位置上的数是 0 的时候，说明 i 位置上的数是不能单独解码的，那么此时 [0, i] 区间上不存在解码方法。因为 i 位置如果单独参与解码，但是解码失败了，那么前面做的努力就全部白费了。此时 dp[i] = 0

<2> 让 i 位置上的数与 i - 1 位置上的数结合解码成一个字母，也存在解码成功和失败

1. 解码成功：当结合的数在 [10, 26] 之间的时候，说明 [i - 1, i] 两个位置是可以解码成功的，那么此时 [0, i] 区间上的解码方法应该等于 [0, i - 2 ] 区间上的解码方法，原因同上。此时 dp[i] = dp[i - 2]
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

**注意：**上面为何设定 dp[i] += dp[i-1] (或 dp[i-2] )，究其原因是为了适应 dp[i] 位置被提前初始化为0的情况，同时避免因为对单独解码和联合解码的逻辑处理先后引起 dp[i] 数值不理想的情况。（例如可以单独解码但是不能联合解码，按照上面情况推断的逻辑需要对 dp[i] 先后赋值为 dp[i-1], 0 ，但是显然可以单独编码这里却因为对逻辑判断的顺序导致了 dp[i] 处值被错误置0的情况）

3. 初始化

由状态转移方程可知，要推导其他位置的值首先需要用到 i - 1, i - 2 位置的dp值，因此需要初始化 dp[0], dp[1] 的值。

对 0,1 位置初始化时，同样需要遵循单独解码与联合解码的要求：

<1> 对 dp[0]:

当 s[0] == ‘0’ 时，没有解码方法，dp[0] = 0

当 s[0] != ‘0’ 时，能单独解码成功，dp[0] = 1

<2> 对 dp[1]:

当 s[1] 在 [1, 9] 之间时，能单独解码，此时 dp[i] += dp[i - 1] （这里dp[0] 的值不论等于1还是0，利用+=刚好可以对应if/else的两种分支对 dp[1] 赋值的情况）

当 s[0] 与 s[1] 结合后的数在 [10, 26] 之间时，说明前两个字符又能组成联合编码，由于 dp[-1] 不存在，所以制定赋值此时 dp[1] += 1

4. 填表顺序

从左往右

5. 返回值

应该返回 dp[n - 1] 的值，因为遍历完字符串中最后一位数字才算结束，表示在 [0, n-1] 区间上总共的解码方法

示例代码：

int numDecodings(string s) {
    // dp[i]表示第i位置解码方法总数
    // 解码方式分两种：1.第i位单独解码  2.第i-1位与第i位组合解码

    int n = s.size();
    vector<int>dp(n, 0);

    // 1.初始化
    dp[0] = s[0] == '0' ? 0 : 1;
    if (n == 1) { return dp[0]; }  // 防止后续越界

    if (s[1] <= '9' && s[1] >= '1') { dp[1] += dp[0]; }     // i=0、1分别解码算一种方法
    int val = (s[0] - '0') * 10 + (s[1] - '0');
    if (val <= 26 && val >= 10) { dp[1] += 1; }

    for (int i = 2; i < n; i++)
    {
        // 单独解码
        if (s[i] <= '9' && s[i] >= '1') { dp[i] += dp[i - 1]; }

        // 与前一位联合解码
        val = (s[i - 1] - '0') * 10 + (s[i] - '0');
        if (val <= 26 && val >= 10)
        {
            dp[i] += dp[i - 2];
        }
    }

    return dp[n - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

总结

​ 对于诸如此类的线性dp数组的题型，最大的共性就是“以 i 位置开始/结束，怎么样怎么样”。我们首先要做的就是确定 dp[i] 表示的是什么，状态转移方程是如何确定dp数组元素之间的推导关系的，接着初始化控制赋值流程，处理边界条件防止越界访问，确定填表顺序和返回值，最后根据思路编写代码。