DP：斐波那契数列模型

1. 引言斐波那契与动态规划的缘分斐波那契数列Fibonacci sequence是算法与数学中最经典的序列之一。对于计算机科学而言它不仅是递归入门的经典例子更是动态规划思想启蒙的绝佳载体。初学者往往先写出一个简单的递归函数然后在计算fib(50)时发现程序“卡死”——这就是动态规划要解决的核心问题重叠子问题。斐波那契数列模型揭示了动态规划的两大要素最优子结构原问题的最优解包含子问题的最优解这里“最优”体现为数值累加。重叠子问题递归过程中反复计算相同的子问题。通过斐波那契我们可以清晰地看到从暴力递归 → 记忆化搜索 → 迭代DP → 空间压缩的完整优化路径。这一过程几乎涵盖了动态规划入门所需的所有核心思想。2. 斐波那契数列的数学本质斐波那契数列定义为F(0)0,F(1)1F(0)0,F(1)1F(n)F(n−1)F(n−2)for n≥2F(n)F(n−1)F(n−2)for n≥2其前几项为0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...数学性质线性齐次递推关系二阶常系数。通项公式比内公式F(n)ϕn−ψn5F(n)5​ϕn−ψn​其中 ϕ152ϕ215​​ 为黄金分割比ψ1−52ψ21−5​​。增长趋势指数级增长ϕn/5ϕn/5​ 近似。在算法题中斐波那契往往不是直接求解而是作为状态转移的模板许多看似复杂的问题经过抽象后其DP方程形式为dp[i] dp[i-1] dp[i-2]或在此基础上增加权重、条件限制。3. 递归解法优雅背后的致命伤3.1 暴力递归实现pythondef fib_recursive(n): if n 0: return 0 if n 1: return 1 return fib_recursive(n-1) fib_recursive(n-2)代码简洁完全贴合数学定义。3.2 时间复杂度分析指数爆炸设 T(n)T(n) 为计算 F(n)F(n) 所需时间则T(n)T(n−1)T(n−2)O(1)T(n)T(n−1)T(n−2)O(1)由特征方程可得 T(n)O(ϕn)T(n)O(ϕn)约为 O(1.618n)O(1.618n)。计算 F(50)F(50) 需要大约 250250 次递归调用这是天文数字。3.3 递归树与重叠子问题画出递归树以 n5 为例textfib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) ... ... ... ...可以看到fib(3)被计算了2次fib(2)被计算了3次。当 n 增大时重复计算量呈指数增长。关键洞察暴力递归没有保存中间结果导致大量重复计算。这正是动态规划的切入点。4. 动态规划初探记忆化搜索自顶向下4.1 备忘录模式引入一个数组或哈希表memo在计算前先查询是否已经计算过。如果计算过直接返回否则计算并存入备忘录。pythondef fib_memo(n, memoNone): if memo is None: memo {} if n in memo: return memo[n] if n 0: return 0 if n 1: return 1 memo[n] fib_memo(n-1, memo) fib_memo(n-2, memo) return memo[n]4.2 复杂度分析与优化效果每个n只会被计算一次因此时间复杂度降为 O(n)O(n)空间复杂度 O(n)O(n)递归栈深度 备忘录空间。这是“用空间换时间”的经典案例。记忆化搜索保留了递归的思维直观性同时消除了冗余计算。5. 动态规划核心状态转移与递推自底向上5.1 DP数组定义定义dp[i]表示斐波那契数列第 i 项的值。初始化dp[0]0,dp[1]1dp[0]0,dp[1]1状态转移方程dp[i]dp[i−1]dp[i−2](i≥2)dp[i]dp[i−1]dp[i−2](i≥2)5.2 迭代实现pythondef fib_dp(n): if n 1: return n dp [0] * (n 1) dp[0] 0 dp[1] 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]5.3 时间复杂度 O(n) 空间复杂度 O(n)自底向上的方式避免了递归栈开销效率更高且更容易理解状态流动的过程。6. 空间压缩的艺术从 O(n) 到 O(1)6.1 滚动数组思想观察状态转移方程dp[i]只依赖于dp[i-1]和dp[i-2]更早的状态不再需要。因此我们不必存储整个数组只需维护两个变量。6.2 只保留前两个状态pythondef fib_optimized(n): if n 1: return n prev2 0 # dp[i-2] prev1 1 # dp[i-1] for i in range(2, n 1): curr prev1 prev2 prev2 prev1 prev1 curr return prev16.3 最优实现代码上述代码的时间复杂度 O(n)O(n)空间复杂度 O(1)O(1)是斐波那契数列求解的最优常规解法。注意当 n 非常大时即使 O(n)O(n) 的时间也可能不够快此时需要矩阵快速幂后文讲解。7. 斐波那契模型的核心特征7.1 线性递推状态转移方程是线性的形式为dp[i] a * dp[i-1] b * dp[i-2] ...。斐波那契是最简单的a1, b1。7.2 最优子结构原问题的解由子问题的解组合而成。在斐波那契中F(n)由F(n-1)和F(n-2)直接相加得到。在变体问题中往往是取最值如最小花费或求和如路径数。7.3 重叠子问题这是动态规划能够优化递归的关键。如果一个问题不具备重叠子问题DP 可能并不适用如分治算法。8. 经典变体一爬楼梯问题8.1 问题描述假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶这是 LeetCode 70 题也是斐波那契的经典变形。8.2 状态定义与转移定义dp[i]表示到达第 i 阶楼梯的方法数。到达第 i 阶可以从第 i-1 阶爬 1 步过来也可以从第 i-2 阶爬 2 步过来。因此dp[i] dp[i-1] dp[i-2]。边界条件dp[1] 1只有 1 种方法dp[2] 211 或 2你会发现dp[1] 1, dp[2] 2正好对应斐波那契数列从第 2 项开始的变种。实际上dp[n] F(n1)。8.3 代码实现与变种一次1/2/3步pythondef climbStairs(n): if n 2: return n dp [0] * (n1) dp[1] 1 dp[2] 2 for i in range(3, n1): dp[i] dp[i-1] dp[i-2] return dp[n]变种如果每次可以爬 1、2、3 步则状态转移变为dp[i]dp[i−1]dp[i−2]dp[i−3]dp[i]dp[i−1]dp[i−2]dp[i−3]此时就是三阶斐波那契Tribonacci序列。9. 经典变体二最小花费爬楼梯9.1 问题引入数组cost的长度为 ncost[i]表示从第 i 阶楼梯向上爬需要支付的费用。你可以选择从下标 0 或 1 开始爬。每次爬 1 或 2 阶。求到达楼顶第 n 阶的最小花费。LeetCode 746 题。相比爬楼梯计数这里变成了最优解最小花费。9.2 状态设计到达 vs 从i出发两种常见状态定义dp[i]表示到达第 i 阶的最小花费到达时已支付 cost[i] 或未支付需明确。dp[i]表示从第 i 阶出发爬到顶部的最小花费。通常采用第二种更清晰定义dp[i]为从第 i 阶台阶开始到达楼顶的最小花费。则dp[i] cost[i] min(dp[i1], dp[i2])。边界dp[n] 0已经到顶无需花费dp[n-1] cost[n-1]。也可以采用第一种但需小心处理。9.3 多种解法对比自顶向下记忆化pythondef minCostClimbingStairs(cost): n len(cost) memo {} def dfs(i): if i n: return 0 if i in memo: return memo[i] memo[i] cost[i] min(dfs(i1), dfs(i2)) return memo[i] return min(dfs(0), dfs(1))自底向上 DP空间压缩pythondef minCostClimbingStairs(cost): n len(cost) prev2 cost[0] # dp[0] prev1 cost[1] # dp[1] for i in range(2, n): curr cost[i] min(prev1, prev2) prev2 prev1 prev1 curr return min(prev1, prev2)这里dp[i]定义为“从第 i 阶出发的最小花费”所以最终答案是min(dp[0], dp[1])。10. 经典变体三打家劫舍House Robber10.1 问题抽象你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你今晚能够偷窃到的最高金额。LeetCode 198 题。这是“不能相邻”的限制下的最优选择问题。10.2 状态转移与斐波那契联系定义dp[i]表示前 i 间房屋能偷到的最大金额。对于第 i 间房屋下标从1开始有两种选择偷则金额为nums[i-1] dp[i-2]不偷则金额为dp[i-1]因此dp[i]max⁡(dp[i−1],dp[i−2]nums[i−1])dp[i]max(dp[i−1],dp[i−2]nums[i−1])边界dp[0] 0没有房屋dp[1] nums[0]这个递推和斐波那契的结构相似只是加法变成了取最大值。空间压缩pythondef rob(nums): prev2 0 # dp[i-2] prev1 0 # dp[i-1] for num in nums: curr max(prev1, prev2 num) prev2 prev1 prev1 curr return prev110.3 环形打家劫舍进阶如果房屋首尾相连成环则需考虑两种情况不偷第一家范围nums[1:]不偷最后一家范围nums[:-1]取两者最大值。这仍建立在斐波那契模型的线性递推基础上。11. 经典变体四不同路径二维斐波那契11.1 网格中的递推一个机器人位于 m x n 网格的左上角每次只能向下或向右移动一步问到达右下角有多少条不同路径LeetCode 62 题。定义dp[i][j]为到达 (i, j) 的路径数。由于只能从上方或左方过来dp[i][j]dp[i−1][j]dp[i][j−1]dp[i][j]dp[i−1][j]dp[i][j−1]边界第一行和第一列均为 1。这实际上是二维的“斐波那契”递推可以压缩为一维数组成为“滚动数组”的典型例子。11.2 组合数学解法 vs DP该问题本质上是组合数从起点到终点需要 m-1 次向下和 n-1 次向右总步数 mn-2选其中 m-1 次向下答案为 C(mn−2,m−1)C(mn−2,m−1)。DP 方法更加通用适用于带障碍物的情况LeetCode 63。12. 斐波那契模型的高阶扩展12.1 矩阵快速幂优化log n 时间对于线性递推可以使用矩阵快速幂将时间复杂度从 O(n) 降到 O(log n)。斐波那契的矩阵形式[F(n)F(n−1)][1110]⋅[F(n−1)F(n−2)][F(n)F(n−1)​][11​10​]⋅[F(n−1)F(n−2)​]通过快速幂计算矩阵的 n 次幂可以在 O(log n) 时间内得到结果。这在 n 极大如 10^18时非常有用。pythondef matrix_mult(a, b): return [[a[0][0]*b[0][0] a[0][1]*b[1][0], a[0][0]*b[0][1] a[0][1]*b[1][1]], [a[1][0]*b[0][0] a[1][1]*b[1][0], a[1][0]*b[0][1] a[1][1]*b[1][1]]] def matrix_pow(matrix, n): result [[1,0],[0,1]] while n: if n 1: result matrix_mult(result, matrix) matrix matrix_mult(matrix, matrix) n 1 return result def fib_log(n): if n 1: return n M [[1,1],[1,0]] M_n matrix_pow(M, n-1) return M_n[0][0]12.2 生成函数与通项公式比内公式虽然给出封闭形式但由于涉及无理数在编程中浮点精度问题使其不适合大数计算但可用于数学分析。12.3 模运算与大数据处理很多题目要求结果对 10971097 取模。只需在每次加法后取模即可同时注意矩阵快速幂中的乘法也要取模。13. 常见错误与调试技巧13.1 边界条件错误忽略 n0 或 n1 的情况。在爬楼梯中对 n2 的处理可能出错。最小花费问题中起点选择是 0 或 1需要 min。13.2 状态定义混淆是“到达 i 的花费”还是“从 i 出发的花费”定义不同转移方程和最终答案都不同。在打家劫舍中dp[i]是前 i 个的最大值还是包含第 i 个的最大值前者更通用。13.3 溢出问题当 n 较大时斐波那契值迅速超过 32 位甚至 64 位整数范围。在不需要取模的题目中应使用大整数Python 自动支持但要注意性能。在 C 中需使用long long或__int128。14. 总结从斐波那契到一般DP思维斐波那契数列模型是动态规划的“Hello World”。它教会我们识别重叠子问题递归树中重复计算的部分。设计状态表示dp[i]通常代表与 i 相关的某种最优值或计数。推导状态转移方程当前状态如何由前几个状态得到线性、取 max/min、求和等。优化空间观察依赖关系利用滚动数组。处理边界初始化正确的前几个状态。当你面对一个新的 DP 问题时可以先尝试套用斐波那契模型的思路看它是否可以用一维 DP状态转移是否只依赖前几个状态是否可以通过类似的空间压缩优化。许多经典问题如“解码方法”、“不同路径 II”、“最长斐波那契子序列”等本质上都是对斐波那契模型的拓展。掌握这个模型你就已经迈入了动态规划的大门。15. 附录完整代码集Python 版python# 1. 递归指数级仅供演示 def fib_recursive(n): if n 1: return n return fib_recursive(n-1) fib_recursive(n-2) # 2. 记忆化搜索 def fib_memo(n, memo{}): if n in memo: return memo[n] if n 1: return n memo[n] fib_memo(n-1, memo) fib_memo(n-2, memo) return memo[n] # 3. DP 自底向上 O(n) 空间 def fib_dp(n): if n 1: return n dp [0] * (n1) dp[1] 1 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] return dp[n] # 4. 空间优化 O(1) def fib_opt(n): if n 1: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b # 5. 爬楼梯 def climbStairs(n): if n 2: return n a, b 1, 2 for _ in range(3, n1): a, b b, a b return b # 6. 最小花费爬楼梯 def minCostClimbingStairs(cost): n len(cost) prev2, prev1 cost[0], cost[1] for i in range(2, n): curr cost[i] min(prev1, prev2) prev2, prev1 prev1, curr return min(prev1, prev2) # 7. 打家劫舍 def rob(nums): prev2, prev1 0, 0 for num in nums: prev2, prev1 prev1, max(prev1, prev2 num) return prev1 # 8. 不同路径 def uniquePaths(m, n): dp [1] * n for i in range(1, m): for j in range(1, n): dp[j] dp[j-1] return dp[-1] # 9. 矩阵快速幂斐波那契 def matrix_mult(A, B): return [[A[0][0]*B[0][0] A[0][1]*B[1][0], A[0][0]*B[0][1] A[0][1]*B[1][1]], [A[1][0]*B[0][0] A[1][1]*B[1][0], A[1][0]*B[0][1] A[1][1]*B[1][1]]] def matrix_pow(M, k): result [[1,0],[0,1]] while k: if k 1: result matrix_mult(result, M) M matrix_mult(M, M) k 1 return result def fib_matrix(n): if n 1: return n M [[1,1],[1,0]] Mn matrix_pow(M, n-1) return Mn[0][0]Java 版javapublic class FibonacciDP { // 空间优化 public static int fib(int n) { if (n 1) return n; int a 0, b 1; for (int i 2; i n; i) { int c a b; a b; b c; } return b; } // 爬楼梯 public static int climbStairs(int n) { if (n 2) return n; int a 1, b 2; for (int i 3; i n; i) { int c a b; a b; b c; } return b; } // 最小花费 public static int minCostClimbingStairs(int[] cost) { int n cost.length; int prev2 cost[0], prev1 cost[1]; for (int i 2; i n; i) { int curr cost[i] Math.min(prev1, prev2); prev2 prev1; prev1 curr; } return Math.min(prev1, prev2); } // 打家劫舍 public static int rob(int[] nums) { int prev2 0, prev1 0; for (int num : nums) { int curr Math.max(prev1, prev2 num); prev2 prev1; prev1 curr; } return prev1; } // 不同路径 public static int uniquePaths(int m, int n) { int[] dp new int[n]; Arrays.fill(dp, 1); for (int i 1; i m; i) { for (int j 1; j n; j) { dp[j] dp[j-1]; } } return dp[n-1]; } }C 版cpp#include vector #include algorithm using namespace std; class Solution { public: int fib(int n) { if (n 1) return n; int a 0, b 1; for (int i 2; i n; i) { int c a b; a b; b c; } return b; } int climbStairs(int n) { if (n 2) return n; int a 1, b 2; for (int i 3; i n; i) { int c a b; a b; b c; } return b; } int minCostClimbingStairs(vectorint cost) { int n cost.size(); int prev2 cost[0], prev1 cost[1]; for (int i 2; i n; i) { int curr cost[i] min(prev1, prev2); prev2 prev1; prev1 curr; } return min(prev1, prev2); } int rob(vectorint nums) { int prev2 0, prev1 0; for (int num : nums) { int curr max(prev1, prev2 num); prev2 prev1; prev1 curr; } return prev1; } int uniquePaths(int m, int n) { vectorint dp(n, 1); for (int i 1; i m; i) { for (int j 1; j n; j) { dp[j] dp[j-1]; } } return dp[n-1]; } };