企业官网建设流程全解析

一、问题：斐波那契数列

斐波那契数列（Fibonacci Sequence）是计算机科学中最经典的入门问题。它的数学定义如下：

• F(0)=0F(0) = 0F(0)=0
• F(1)=1F(1) = 1F(1)=1
• F(2)=1F(2) = 1F(2)=1
• 当n>2n > 2n>2时，F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)

展开前几项：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

相邻两项的比值F(n+1)F(n)\frac{F(n+1)}{F(n)}F(n)F(n+1)​会无限趋近于黄金分割比ϕ≈1.618\phi \approx 1.618ϕ≈1.618。但在算法领域，斐波那契数列真正的价值不在于数列本身，而在于它完美展示了"重叠子问题"和"动态规划"的核心思想，是理解 DP 最理想的起点。

二、暴力递归：最直觉但最慢的解法

按照数学定义，最直觉的写法就是直接翻译成递归函数：

publicstaticintfib(intN){if(N==0)return0;if(N==1||N==2)return1;returnfib(N-1)+fib(N-2);}

递归的终止条件

if(N==0)return0;if(N==1||N==2)return1;

这三行叫递归的"出口"或"边界条件"。斐波那契数列的 base case 是F(0)=0F(0)=0F(0)=0、F(1)=1F(1)=1F(1)=1、F(2)=1F(2)=1F(2)=1。当N走到这些值的时候，函数不再往下递归，直接返回已知结果。如果没有这些终止条件，递归会一直往下调用到负数，最终栈溢出崩溃。

致命问题：指数级的时间复杂度

虽然代码简洁，但效率极低。以fib(5)为例，递归调用过程如下：

fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ fib(2) fib(1)

可以看到：

• fib(3)被计算了2 次
• fib(2)被计算了3 次

当N更大时，这种重复呈指数级增长。计算fib(20)时，fib(18)会被重复计算成千上万次。时间复杂度约为O(2n)O(2^n)O(2n)，空间复杂度是递归调用栈的深度O(n)O(n)O(n)。

根本原因：存在大量重叠子问题（Overlapping Subproblems），同一个子问题被反复求解。

💡核心心法：千万不要看不起暴力解法，动态规划问题最困难的就是写出这个暴力解法，即状态转移方程。只要写出暴力解法，优化方法无非是用"备忘录"或者 DP table，再无奥妙可言。

三、备忘录递归：自顶向下 + 记忆化

既然同一个子问题会被重复计算，那我们只要算过一次就记下来，下次直接用，不就行了？

这就是**备忘录（Memoization）**的思想：

importjava.util.HashMap;importjava.util.Map;publicstaticintfibMemo(intN){Map<Integer,Integer>memo=newHashMap<>();returnhelper(N,memo);}privatestaticinthelper(intN,Map<Integer,Integer>memo){if(N==0)return0;if(N==1||N==2)return1;if(memo.containsKey(N))returnmemo.get(N);// 算过了，直接返回intres=helper(N-1,memo)+helper(N-2,memo);// 没算过，递归求解memo.put(N,res);// 算完存起来returnres;}

效果：

• 每个子问题只计算一次，时间复杂度降为O(n)O(n)O(n)
• 空间复杂度：O(n)O(n)O(n)（备忘录哈希表 + 递归栈）

备忘录本质上还是递归，只是"带记忆的递归"。它从大问题出发，拆到小问题，碰到算过的就直接返回——这叫自顶向下。

四、DP 数组：自底向上填表

如果我们把备忘录独立出来变成一张完整的表，然后用循环从最小的子问题开始，一步步推到最终答案，这就是动态规划（Dynamic Programming）的标准写法。

核心思想

Java 实现（DP 数组版）

publicstaticintfibDP(intN){if(N==0)return0;if(N==1||N==2)return1;// dp[i] 表示第 i 个斐波那契数 F(i)int[]dp=newint[N+1];// 长度 N+1，下标 0 ~ N，默认全 0// 对应 C++ 的 vector<int> dp(N + 1, 0);// Base cases：填好已知的"地基"dp[1]=1;dp[2]=1;// 从底向上，一步步推导for(inti=3;i<=N;i++){dp[i]=dp[i-1]+dp[i-2];// 状态转移方程}returndp[N];// 直接取答案}

状态转移方程

书上给出的数学形式：

f(n)={1,n=1,2f(n−1)+f(n−2),n>2f(n) = \begin{cases} 1, & n=1,2 \\ f(n-1)+f(n-2), & n>2 \end{cases}f(n)={1,f(n−1)+f(n−2),​n=1,2n>2​

为什么叫"状态转移"？把f(n)f(n)f(n)想作一个状态nnn，这个状态由状态n−1n-1n−1和状态n−2n-2n−2相加"转移"而来。状态转移方程直接代表着暴力解法，它是问题的核心。

以 N=5 走一遍

初始：dp = [0, 1, 1, 0, 0, 0]

返回dp[5] = 5✓

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

五、状态压缩：空间降到 O(1)

🔑关键洞察：根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的 DP table 来存储所有状态，只要想办法存储之前的两个状态就行了。

这就是状态压缩：如果发现每次状态转移只需要 DP table 中的一部分，就可以缩小 DP table 的大小，只记录必要的数据。上面例子相当于把 DP table 的大小从NNN缩小到 2。

书上 C++ 代码

intfib(intN){if(N==0)return0;if(N==2||N==1)return1;intprev=1,curr=1;for(inti=3;i<=N;i++){intsum=prev+curr;prev=curr;curr=sum;}returncurr;}

Java 实现

publicstaticintfibCompressed(intN){if(N==0)return0;if(N==1||N==2)return1;intprev=1;// F(n-2)，初始对应 F(1)=1intcurr=1;// F(n-1)，初始对应 F(2)=1for(inti=3;i<=N;i++){intsum=prev+curr;// 当前值 = 前两项之和prev=curr;// 滚动：旧的"前一项"变成"前前项"curr=sum;// 滚动：当前值变成新的"前一项"}returncurr;}

以 N=5 走一遍

返回curr = 5✓

时间复杂度：O(n)O(n)O(n)，空间复杂度：O(1)O(1)O(1)—— 这是面试中最推荐的写法。

📌延伸：后续动态规划章节还会看到，一般来说是把一个二维的 DP table 压缩成一维，即把空间复杂度从O(n2)O(n^2)O(n2)压到O(n)O(n)O(n)。状态压缩是 DP 优化中极为重要的一课。

六、四种方法完整对比

七、从斐波那契到真正的动态规划

⚠️重要澄清：斐波那契数列的例子严格来说不算动态规划，因为没有涉及求最值，以上旨在说明重叠子问题的消除方法，演示为得到最优解法而逐步求精的过程。

真正的动态规划问题通常包含"求最值"这一要素。比如凑零钱问题（LeetCode 322）：

• 给定 k 种硬币，面值c1, c2, ..., ck，数量无限
• 目标金额amount
• 求凑出amount所需的最少硬币数，凑不出返回 -1

函数签名：

intcoinChange(int[]coins,intamount);

示例：coins = [1, 2, 5], amount = 11→5 + 5 + 1 = 3枚

思考路径和斐波那契完全一样：

1. 先写暴力（递归枚举所有凑法）
2. 发现重叠子问题→ 加备忘录 / 改自底向上 DP
3. 找状态转移：dp[i] = min(dp[i-c]) + 1（对所有可行硬币 c）
4. 看能否状态压缩（这个一维可以压缩，但保留数组语义更清晰）

八、核心心法总结

千万不要看不起暴力解法，动态规划问题最困难的就是写出这个暴力解法，即状态转移方程。只要写出暴力解法，优化方法无非是用"备忘录"或者 DP table，再无奥妙可言。

状态转移方程直接代表着暴力解法，它是问题的核心。

状态压缩：每次状态转移只需要 DP table 中的一部分，可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据。

斐波那契数列虽然简单，但它浓缩了动态规划的全部优化思路：暴力递归 → 发现重叠子问题 → 备忘录消除重复 → DP table 系统化 → 状态压缩极致优化。当你以后面对背包、最长公共子序列、股票买卖等复杂 DP 问题时，思路都是这条路径的延伸。斐波那契就是那把打开 DP 大门的钥匙。🔑