动态规划入门：斐波那契模型与LeetCode实战

1. 动态规划入门：从斐波那契模型理解问题分解

动态规划（Dynamic Programming）作为算法设计中的重要方法论，其核心思想是通过将复杂问题分解为相互关联的子问题来降低求解难度。斐波那契数列问题（Fibonacci Sequence）堪称理解动态规划最经典的入门案例——每个数都是前两个数之和的简单定义，却蕴含着重叠子问题和最优子结构这两个动态规划的关键特性。

在实际编程面试和算法竞赛中，许多问题都可以转化为斐波那契数列模型的变体。今天我们将深入分析两个典型问题："使用最小花费爬楼梯"（LeetCode 746）和"解码方法"（LeetCode 91）。通过这两个案例，您不仅能够掌握动态规划的基本应用模式，还能学会如何识别问题中的斐波那契特征。

2. 最小花费爬楼梯问题解析

2.1 问题描述与直观理解

LeetCode 746题要求我们计算到达楼梯顶部的最小花费。给定一个整数数组cost，其中cost[i]表示踏在第i级台阶所需支付的费用。每次可以选择爬1级或2级台阶，可以从下标为0或1的台阶开始爬楼梯。我们的目标是找出到达顶部（即数组末尾之后的位置）的最小总花费。

例如对于cost = [10,15,20]：

• 路径1：从下标0开始(花费0)，支付10到下标1，支付15到下标2，支付20到顶部 → 总花费45
• 路径2：从下标1开始(花费0)，支付15直接到下标2，支付20到顶部 → 总花费35 显然最优解是35

2.2 动态规划五步法详细实现

2.2.1 状态表示设计

我们定义dp[i]为到达第i级台阶时的最小累计花费（注意：站在i级台阶时尚未支付cost[i]）。这种定义方式符合"以i位置为结尾"的常见动态规划状态表示原则，同时巧妙地处理了起始条件和支付时机。

关键点说明：

• dp数组长度为n+1（n是cost数组长度），因为顶部是第n级台阶
• dp[0]和dp[1]初始化为0，因为可以直接选择从这两级开始而不需支付

2.2.2 状态转移方程推导

对于i≥2的情况，到达i级台阶只有两种可能：

1. 从i-1级跨1步上来，总花费=到达i-1级的花费dp[i-1] + 跨步支付的cost[i-1]
2. 从i-2级跨2步上来，总花费=到达i-2级的花费dp[i-2] + 跨步支付的cost[i-2]

因此状态转移方程为： dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

2.2.3 边界条件处理

初始化dp[0] = dp[1] = 0，这对应于题目允许从第0级或第1级开始的选择自由。这种初始化方式确保了状态转移的正确基础。

2.2.4 填表顺序确定

根据状态转移方程，dp[i]依赖于dp[i-1]和dp[i-2]，因此应采用从左到右的顺序填充dp表。这种顺序保证了在计算每个状态时，其所依赖的前置状态都已被正确计算。

2.2.5 最终结果获取

由于顶部是第n级台阶（cost数组长度n），所以返回dp[n]作为最终结果。

2.3 C++实现与优化技巧

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

空间优化版本（使用滚动变量）：

class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int prev = 0, curr = 0; for (int i = 2; i <= cost.size(); ++i) { int next = min(curr + cost[i-1], prev + cost[i-2]); prev = curr; curr = next; } return curr; } };

关键提示：在面试中，实现基础版本后可以主动提出空间优化方案，展示对算法理解的深度。但要注意先确保正确性再考虑优化。

3. 解码方法问题深度剖析

3.1 问题描述与复杂性分析

LeetCode 91题要求我们计算数字字符串解码成字母组合的所有可能方式。规则如下：

• 'A'→'1', 'B'→'2', ..., 'Z'→'26'
• 有效解码不能包含前导零（如"06"不能解码为'F'）

例如："226"可以解码为：

1. "BZ" (2 26)
2. "VF" (22 6)
3. "BBF" (2 2 6) 共3种方式

3.2 动态规划解决方案设计

3.2.1 状态表示精确定义

定义dp[i]为字符串前i个字符的解码方法总数。这种定义方式符合线性动态规划的典型模式，其中每个状态表示问题在某个规模下的完整解。

3.2.2 状态转移方程全面考虑

对于每个位置i，我们需要考虑两种解码可能性：

1. 单独解码s[i]（要求s[i]≠'0'）：
   • 有效时：dp[i] += dp[i-1]
2. 组合解码s[i-1]和s[i]（要求组合数在10-26之间）：
   • 有效时：dp[i] += dp[i-2]

特别注意边界情况：

• 空字符串有1种解码方式（dp[0]=1）
• 单个字符时，'0'无效，其他有效

3.2.3 初始化细节处理

初始化需要特别小心：

dp[0] = 1; // 空字符串有1种解码方式 dp[1] = (s[0] != '0') ? 1 : 0;

3.2.4 填表顺序与实现

采用从左到右的顺序填充dp表，注意处理i=1时的特殊情况以避免数组越界。

3.3 C++实现与边界处理

基础版本：

class Solution { public: int numDecodings(string s) { int n = s.size(); vector<int> dp(n + 1); dp[0] = 1; dp[1] = s[0] != '0' ? 1 : 0; for (int i = 2; i <= n; ++i) { // 单独解码当前字符 if (s[i-1] != '0') { dp[i] += dp[i-1]; } // 尝试组合解码前两个字符 int twoDigit = stoi(s.substr(i-2, 2)); if (twoDigit >= 10 && twoDigit <= 26) { dp[i] += dp[i-2]; } } return dp[n]; } };

优化版本（节省空间）：

class Solution { public: int numDecodings(string s) { int n = s.size(); int prevPrev = 1, prev = s[0] != '0' ? 1 : 0; for (int i = 2; i <= n; ++i) { int current = 0; if (s[i-1] != '0') { current += prev; } int twoDigit = stoi(s.substr(i-2, 2)); if (twoDigit >= 10 && twoDigit <= 26) { current += prevPrev; } prevPrev = prev; prev = current; } return prev; } };

3.4 易错点与特殊测试用例

需要特别注意的测试用例：

1. 以'0'开头的字符串："011"→0
2. 包含"00"的字符串："100"→0
3. 有效组合后跟零："110"→1
4. 连续有效组合："226"→3
5. 单个字符："9"→1，"0"→0

调试技巧：在纸上画出dp表，手动计算前几个值，确保转移逻辑正确。特别注意0的处理和组合解码的有效范围。

4. 动态规划解题的通用方法论

4.1 识别问题特征的技巧

判断问题是否适合用动态规划解决，可以考察以下特征：

1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：递归求解时会重复计算相同的子问题
3. 无后效性：当前状态一旦确定，后续决策不受之前决策影响

斐波那契类问题的典型特征：

• 当前状态只与有限个前驱状态相关
• 状态转移呈现加法或取最值的形式
• 通常有O(n)时间复杂度的解法

4.2 状态设计的心得体会

有效的状态设计是动态规划成功的关键：

1. 尝试"以i结尾"或"前i个元素"的形式定义状态
2. 状态应包含足够信息来确定后续转移
3. 状态空间不宜过大（通常一维或二维）
4. 必要时可以增加辅助状态维度

4.3 编码实现的注意事项

编写动态规划代码时的实用建议：

1. 先写注释规划好步骤（创建表、初始化、填表、返回）
2. 仔细处理边界条件（特别是数组起始和结束位置）
3. 使用有意义的变量名（如dp而不是f）
4. 考虑空间优化可能性（滚动数组、变量复用）
5. 添加防御性代码检查输入有效性

4.4 调试与验证策略

确保动态规划正确性的方法：

1. 用小规模测试用例手动计算验证
2. 打印中间dp表检查数值变化
3. 对比暴力解的结果（对小规模输入）
4. 考虑极端情况（空输入、全0、最大值等）
5. 使用静态分析工具检查数组越界

5. 斐波那契模型问题的扩展思考

5.1 相关LeetCode题目推荐

1. 爬楼梯（70题）：最基本的斐波那契变体
2. 打家劫舍（198题）：加入间隔限制条件
3. 多米诺和托米诺平铺（790题）：二维扩展
4. 最长递增子序列（300题）：状态转移更复杂
5. 单词拆分（139题）：结合哈希表使用

5.2 算法优化进阶方向

对于斐波那契类问题，还存在更高效的算法：

1. 矩阵快速幂：将时间复杂度优化到O(logn)
2. 通项公式法：直接数学计算（可能有精度问题）
3. 预处理打表：对于多次查询的情况

5.3 实际工程中的应用场景

动态规划在真实系统中的典型应用：

1. 路径规划中的最短路径计算
2. 资源分配中的最优解寻找
3. 生物信息学中的序列比对
4. 金融领域的投资组合优化
5. 自然语言处理中的分词算法

掌握动态规划不仅有助于算法面试，更是解决复杂工程问题的利器。建议从斐波那契模型入手，逐步扩展到背包问题、图算法等更复杂的领域，建立系统的动态规划思维体系。