动态规划入门：斐波那契模型四题详解（含空间优化技巧）-EW帮帮网

动态规划入门：斐波那契模型四题详解（含空间优化技巧）

动态规划

什么是动态规划？

动态规划（Dynamic Programming，DP）是一种用于解决复杂优化问题的算法设计方法。其核心思想是通过将原问题分解为相互重叠的子问题，并保存子问题的解（称为“状态”），避免重复计算，从而显著提高效率。动态规划适用于具有以下两个关键性质的问题：

重叠子问题（Overlapping Subproblems）：
问题可以被分解为多个重复出现的子问题。例如，斐波那契数列中计算 F(n) 需要重复计算 F(n-1) 和 F(n-2)。
最优子结构（Optimal Substructure）：
问题的最优解可以通过子问题的最优解组合得到。例如，最短路径问题中，若路径 A→B→C 是 A→C 的最短路径，则 A→B 和 B→C 也必须是各自段的最短路径。

什么时候要用动态规划？

以下情况适合使用动态规划：

问题可分解为重叠子问题：如斐波那契数列、背包问题。
需要多次查询子问题的解：如计算编辑距离时，多次查询子串的编辑操作。
需要避免重复计算：如递归解法中存在大量重复计算（时间复杂度高）。
问题的最优解依赖子问题的最优解：如最长递增子序列、矩阵链乘法。

动态规划问题的分支

动态规划问题根据结构和优化目标的不同，可分为以下几类：

分支类型	特点	经典问题
线性动态规划	状态定义在一维或二维序列上，按顺序递推。	斐波那契数列、最长公共子序列
树形动态规划	状态定义在树结构的节点上，通常通过后序遍历求解。	二叉树中的最大路径和
状态压缩动态规划	通过位运算或其他技巧压缩状态表示，减少空间复杂度。	旅行商问题（TSP）
区间动态规划	状态定义在区间上（如 `dp[i][j]` 表示区间 `i` 到 `j` 的解）。	矩阵链乘法、石子合并问题
背包动态规划	解决资源分配问题，状态表示容量约束下的最优选择。	0-1背包、完全背包问题
数位动态规划	处理数字各位上的约束条件，如统计满足特定条件的数字数量。	数字1的个数统计

解决动态规划问题的一般步骤

状态表示：明确 dp 数组（或哈希表）的含义
状态转移方程：根据子问题之间的关系，推导状态转移方程
初始化：设置初始状态和边界条件
填表顺序：确定状态的计算顺序，通常有两种方式——自顶向下、自底向上
返回值：
其他：如空间优化、边界处理

总结

动态规划通过分解问题、存储子问题解、避免重复计算，高效解决具有重叠子问题和最优子结构的复杂问题。掌握定义状态、推导转移方程、初始化和优化的技巧，并通过大量练习熟悉不同分支的典型问题（如背包、LCS、编辑距离等），是提升动态规划能力的关键。

斐波那契数列模型例题

第N个泰波那契数

题目链接：

第N个泰波那契数

要点：

状态定义：dp[i] 表示第 i 个泰波那契数的值
状态转移：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
空间优化：使用滚动数组将空间复杂度从 O(n) 降至 O(1)

老师代码：

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0 || n == 1) return n;

        vector<int> dp(n + 1); // dp[i] 表⽰：第 i 个泰波那契数的值。
        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];
    }
};

我的代码：

使用记忆化搜索解决：

class Solution 
{
    vector<int> memo;
public:
    int tribonacci(int n) 
    {
        if(n == 0) return 0;
        else if(n == 1 || n == 2) return 1;
        
        memo = vector<int>(n + 1);
        memo[0] = 0, memo[1] = 1, memo[2] = 1;
        

        for(int i = 3; i <= n; i++)
        {
            memo[i] = memo[i - 1] + memo[i - 2] + memo[i - 3];
        }    
        return memo[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;
        
        for(int i = 3; i <= n; i++)
        {
            d = a + b + c;
            a = b; b = c; c = d;
        }

        return d;
    }
};

我的思路：

递归改迭代：直接按公式递推，避免递归栈溢出
滚动数组优化：仅保留最近三个值 (a, b, c)，迭代更新
边界处理：n=0 返回 0，n=1 或 n=2 返回 1

我的笔记:

初始代码中 vector<int> dp(n+1) 的空间复杂度为 O(n)，但实际只需保存前三个值
滚动数组通过变量复用 (a = b; b = c; c = d) 实现空间优化
时间复杂度 O(n)，空间复杂度 O(1)

三步问题

题目链接：

三步问题

要点：

状态定义：dp[i] 表示到达第 i 阶台阶的方法数
状态转移：dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD
取模技巧：每次加法后立即取模，防止整数溢出

老师代码：

class Solution {
public:
    const int MOD = 1e9 + 7;
    int waysToStep(int n) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回
        // 处理边界情况
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;
        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 || n == 2) return n;
        else if(n == 3) return 4;

        const int mod = 1e9 + 7;
        //初始化
        int a = 1, b = 2, c = 4, d;//其中a为n == 1，b为n == 2，c为n == 3，d为我们要求的
        
        //填表
        for(int i = 4; i <= n; i++)
        {
            d = (a % mod + b % mod) % mod + c % mod;
            a = b, b = c, c = d;
        }

        return d % mod;
    }
};

我的思路：

递推关系：每一步可从 i-1, i-2, i-3 跳过来，方法数累加
滚动数组优化：用 a, b, c 代替 dp[i-3], dp[i-2], dp[i-1]
边界处理：n=1 返回 1，n=2 返回 2，n=3 返回 4

我的笔记:

取模操作
比较大的数的科学表示法
```
int mod = 1e9 + 7;
```
题目要求结果对 1e9+7 取模，需在每次加法后立即取模
大数处理：使用 long long 暂存中间结果（若数值范围超过 int）
滚动数组将空间复杂度从 O(n) 优化至 O(1)

使用最小花费爬楼梯

题目链接：

使用最小花费爬楼梯

要点：

状态定义：
- 正向定义：dp[i] 表示到达第 i 阶的最小花费
- 逆向定义：dp[i] 表示从第 i 阶到终点的最小花费
状态转移：
- 正向：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
- 逆向：dp[i] = cost[i] + min(dp[i+1], dp[i+2])

老师代码：

class Solution
{
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        int n = cost.size();
        
        // 初始化⼀个 dp表
        vector<int> dp(n + 1, 0);
        
        // 初始化
        dp[0] = dp[1] = 0;
        
        // 填表
        for (int i = 2; i < n + 1; i++)
        // 根据状态转移⽅程得
        dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);
        
        // 返回结果
        return dp[n];
    }
};

我的代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //边界问题
        if(cost.size() < 2) return 0;

        //状态列表    
        vector<int> dp(cost.size() + 1);//存放到达i位置的最小花费 

        //初始化
        dp[0] = dp[1] = 0;

        //填表
        for(int i = 2; i <= cost.size(); i++)
        {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);//计算最小的花费方式
        }
        
        //返回值
        return dp[cost.size()];
    }
};

第二种思路：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int m = cost.size();
        //状态表示
        vector<int> dp(m);//存放从i位置到楼顶的最小花费

        //初始化
        dp[m - 1] = cost[m - 1];
        dp[m - 2] = cost[m - 2];

        //填表
        for(int i = m - 3; i >= 0; i--)//从后往前填
        {
            dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);
        }

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

我的思路：

正向递推：从起点出发，逐步计算每层最小花费
逆向递推：从终点回退，利用后效性无偏序问题
边界处理：dp[0] = dp[1] = 0（正向）或 dp[n-1] = cost[n-1]（逆向）

我的笔记:

要注意题目要求：我们需要跨过所有台阶，因此最后一个台阶也要跨过到cost.size()位置才算完全跨过，而不是停留在最后一个台阶上
一定要自己推状态表示（dp数组），这是最基本的，最重要的
正向递推需注意终点是 dp[n]（跨过最后一阶）
逆向递推需初始化最后两阶，并最终返回 min(dp[0], dp[1])
时间复杂度 O(n)，空间复杂度 O(n)（可优化为 O(1)）

解码方法

题目链接：

解码方法

要点：

状态定义：dp[i] 表示前 i 个字符的解码方法数
状态转移：
- 单独解码：s[i] != '0' → dp[i] += dp[i-1]
- 联合解码：s[i-1..i] 构成 10~26 → dp[i] += dp[i-2]
虚拟节点：在 dp 数组前添加虚拟节点 dp[0] = 1，简化边界处理

老师代码：

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

使⽤添加辅助结点的⽅式初始化

class Solution
{
public:
    int numDecodings(string s)
    {
        // 优化
        int n = s.size();
        vector<int> dp(n + 1);
        dp[0] = 1; // 保证后续填表是正确的
        dp[1] = s[0] != '0';
        // 填表
        for (int i = 2; i <= n; i++)
        {
            // 处理单独编码
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            // 如果和前⾯的⼀个数联合起来编码
            int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if (t >= 10 && t <= 26) dp[i] += dp[i - 2];
        }
        return dp[n];
    }
};

老师思路：

状态表⽰：根据以往的经验，对于⼤多数线性 dp ，我们经验上都是「以某个位置结束或者开始」做⽂章，这⾥我们继续尝试「⽤ i 位置为结尾」结合「题⽬要求」来定义状态表⽰。

dp[i] 表⽰：字符串中 [0，i] 区间上，⼀共有多少种编码⽅法。
状态转移⽅程：定义好状态表⽰，我们就可以分析 i 位置的 dp 值，如何由「前⾯」或者「后⾯」的信息推导出来。关于 i 位置的编码状况，我们可以分为下⾯两种情况：
- 让 i 位置上的数单独解码成⼀个字⺟；
- 让 i 位置上的数与 i - 1 位置上的数结合，解码成⼀个字⺟。
下⾯我们就上⾯的两种解码情况，继续分析
- 让 i 位置上的数单独解码成⼀个字⺟，就存在「解码成功」和「解码失败」两种情况：
  - i. 解码成功：当 i 位置上的数在 [1, 9] 之间的时候，说明 i 位置上的数是可以单独解码的，那么此时 [0, i] 区间上的解码⽅法应该等于 [0, i - 1] 区间上的解码⽅法。因为 [0, i - 1] 区间上的所有解码结果，后⾯填上⼀个 i 位置解码后的字⺟就可以了。此时 dp[i] = dp[i - 1] ；
  - ii. 解码失败：当 i 位置上的数是 0 的时候，说明 i 位置上的数是不能单独解码的，那么此时 [0, i] 区间上不存在解码⽅法。因为 i 位置如果单独参与解码，但是解码失败了，那么前⾯做的努⼒就全部⽩费了。此时 dp[i] = 0 。
- 让 i 位置上的数与 i - 1 位置上的数结合在⼀起，解码成⼀个字⺟，也存在「解码成功」和「解码失败」两种情况：
  - i. 解码成功：当结合的数在 [10, 26] 之间的时候，说明 [i - 1, i] 两个位置是可以解码成功的，那么此时 [0, i] 区间上的解码⽅法应该等于 [0, i - 2 ] 区间上的解码⽅法，原因同上。此时 dp[i] = dp[i - 2] ；
  - ii. 解码失败：当结合的数在 [0, 9] 和 [27 , 99] 之间的时候，说明两个位置结合后解码失败（这⾥⼀定要注意 00 01 02 03 04 … 这⼏种情况），那么此时 [0, i] 区间上的解码⽅法就不存在了，原因依旧同上。此时 dp[i] = 0 。
我的代码：

class Solution 
{
public:
    int numDecodings(string s) 
    {
        int m = s.size();
        //状态表示
        vector<int> dp(m);
        //初始化
        if(s[0] == '0') dp[0] = 0;
        else dp[0] = 1;
        //边界情况
        if(m == 1) return dp[0];
        //继续初始化
        if(s[1] == '0')//不能单独解码
        {
            if(s[0] == '1' || s[0] == '2') dp[1] = 1;//前一个数有效
            else dp[1] = 0;//前一个数无效
        }
        else//可以单独解码 + 1
        {
            if(s[0] == '1') //前一个数有效
            {
                if(s[1] >= '0' && s[1] <= '9')//当前位置有效
                    dp[1] = 2;
                else//当前位置无效
                    dp[1] = 1;
            }
            else if(s[0] == '2')
            {
                if(s[1] >= '0' && s[1] <= '6')//当前位置有效
                    dp[1] = 2;
                else//当前位置无效
                    dp[1] = 1;
            }
            else //前一个数无效，单独接解码
            {
                if(s[0] == '0') dp[1] = 0;
                else dp[1] = 1;
            }
        }

        //填表
        for(int i = 2; i < m; i++)
        {
            dp[i] = ((s[i] != '0') ? dp[i - 1] : 0) + 
                    (((s[i - 1] == '1' && s[i] >= '0' && s[i] <= '9') || 
                    (s[i - 1] == '2' && s[i] >= '0' && s[i] <= '6')) ? dp[i - 2] : 0); 
        }

        return dp[m - 1];
    }
};

优化后的代码：


class Solution {
public:
    int numDecodings(string s) {
        int m = s.size();
        vector<int> dp(m + 1);

        //初始化
        dp[0] = 1;//当我们填dp[2]的时候就会用到dp[0]中的值，这一个节点为虚拟节点
        if(s[0] == '0') dp[1] = 0;
        else dp[1] = 1;

        //填表
        for(int i = 2; i <= m; i++)
        {
            if(s[i - 1] != '0') dp[i] += dp[i - 1];//第一种解码方法
            int n = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if(n >= 10 && n <= 26) dp[i] += dp[i - 2];//第二种解码方法
        }

        return dp[m];
    }
};

我的思路：

第一段代码：我的解决方法是不把字符串转换为数字直接通过比较每一位的字符大小进行求解，这种方法真的不推荐，因为很容易忽略某些情况导致出错，比如s[i - 1] == 1和s[i - 1] == 2需要分别进行处理，因为当s[i - 1] == 1 时s[i] 可以取1~9；但当s[i - 1] == 2的时候，s[i]只能取1~6，这样就会非常麻烦，建议使用老师的那种方法

第二段代码（优化后）：思路就是老师讲的，我们把原来(老师的代码)的dp表填表的顺序整体向前移动一个位置，这样就可以避免复杂的初始化问题，注意以下几点：

虚拟节点里面的值，要保证后面的填表是正确的。只有当我们填写dp[2]的时候就可能会用到dp[0]中的值，此时我们填写的s中对应位置为i - 1，那么什么时候用到呢？就是在找它的第二种解码方法的时候，如果能解码，dp[2]就要加1，因此dp[0] = 1；
下标映射关系。在填写dp[i]时我们实际是在找s[i - 1]位置的解码次数。
虚拟节点技巧：避免处理 i=0 和 i=1 的特殊情况
字符到数字转换：(s[i-1] - '0') * 10 + (s[i] - '0')
边界处理：首字符为 '0' 直接返回 0

我的笔记:

虚拟节点 dp[0] = 1 使得 dp[2] 的计算逻辑统一（无需特判 i=1）

时间复杂度 O(n)，空间复杂度 O(n)

关键陷阱：连续 '0'（如 "00"）或无效联合编码（如 "27"）需跳过

注意事项总结

C++语法相关：

数组初始化：vector dp(n+1, 0) 显式初始化避免未定义行为

取模操作：大数问题中每次运算后立即取模，防止溢出

字符处理：s[i] - ‘0’ 将字符转换为数字，注意越界检查

算法思路相关：

状态定义：明确 dp[i] 含义（如“到达第 i 阶”或“前 i 个字符”）

转移方程推导：从问题描述中提取子问题关系（如斐波那契递推式）

边界处理：

泰波那契数中 n=0,1,2 直接返回

解码方法中首字符为 ‘0’ 直接返回 0

空间优化：滚动数组适用于仅依赖前几个状态的递推

虚拟节点技巧：简化边界条件处理（如解码方法问题）

常见陷阱：

整数溢出：在取模问题中未及时取模

无效状态转移：如解码方法中 ‘0’ 不能单独解码

下标映射错误：dp 数组下标与实际字符位置偏移

动态规划入门：斐波那契模型四题详解（含空间优化技巧）