📖 动态规划专题怎么用？
动态规划的核心：当前状态只依赖前几个状态。斐波那契、爬楼梯、最大子序和是 DP 的三道入门必刷题。
本专题包含 3 道题，都是外企面试高频真题。每道题按统一结构讲解：
- 题目描述 — 用人话翻译，不用读三遍才懂
- 生活类比 — 把抽象问题变成熟悉的生活场景
- 暴力思路 → 优化思路 — 面试官想看到的思考过程
- IDE 代码 — 带注释的 JS 实现 + 行号
- 复杂度分析 — 时间/空间，面试必问
- 面试加分项 — 能说出来的额外思考
复习建议：先看生活类比理解问题本质，再看思路建立解题框架，最后手写代码 3 遍形成肌肉记忆。面试时先口述思路，确认无误后再写代码。
1斐波那契数列 (Fibonacci) Easy
题目（人话版）
斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21...。规则是每个数 = 前面两个数之和。求第 n 个数。
💡 生活类比：就像你每个月存钱——第一个月存 0，第二个月存 1，之后每个月存的钱 = 上个月存的 + 上上个月存的。随着时间推移，存款越来越多，增长越来越快。
方法一：递归（最直觉但有陷阱）
fib-recursive.js
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
递归的致命问题：时间复杂度 O(2ⁿ)！因为 fib(5) 会计算 fib(4)+fib(3)，fib(4) 又算 fib(3)+fib(2)……fib(3) 被算了两次，fib(2) 算了三次。指数级爆炸。n=40 时浏览器就要卡好几秒。面试官一定追问"能优化吗？"
方法二：迭代法（面试标准答案）
只记住前两个数，一路往后加。不需要递归，也不需要数组。
fib-iterative.js
function fib(n) {
if (n <= 1) return n;
let prev = 0; // 前一个数（fib(0)）
let curr = 1; // 当前数（fib(1)）
for (let i = 2; i <= n; i++) {
const next = prev + curr; // 下一个 = 前两个之和
prev = curr; // 整体往后挪一步
curr = next;
}
return curr;
}
| 方法 | 时间 | 空间 | 问题 |
|---|
| 递归 | O(2ⁿ) | O(n) 栈 | 大量重复计算，n>40 就卡 |
| 迭代 | O(n) | O(1) | ✅ 只记两个变量，又快又省 |
| 递归+缓存 | O(n) | O(n) | ✅ 能写出来是加分项 |
2爬楼梯 (Climbing Stairs) Easy
题目（人话版）
你在爬楼梯，每次可以爬 1 步或 2 步。爬到第 n 阶有多少种方法？
- n=1：1 种（爬 1 步）
- n=2：2 种（1+1 或 2）
- n=3：3 种（1+1+1、1+2、2+1）
- n=4：5 种（1+1+1+1、1+1+2、1+2+1、2+1+1、2+2）
💡 发现规律：1, 2, 3, 5, 8... 这不就是斐波那契数列吗？！为什么？因为到达第 n 阶只有两种可能：从第 n-1 阶爬 1 步上来，或者从第 n-2 阶爬 2 步上来。所以方法数 = 到 n-1 阶的方法 + 到 n-2 阶的方法。
到达第 n 阶 = 到 n-1 阶的方法 + 到 n-2 阶的方法
climbStairs.js
function climbStairs(n) {
if (n <= 2) return n;
let prev1 = 1; // 到 n-2 阶的方法数
let prev2 = 2; // 到 n-1 阶的方法数
for (let i = 3; i <= n; i++) {
const curr = prev1 + prev2; // f(n) = f(n-1) + f(n-2)
prev1 = prev2;
prev2 = curr;
}
return prev2;
}
时间 O(n)，空间 O(1)。和斐波那契一模一样的迭代写法。
面试加分项：主动说出"这道题本质就是斐波那契数列，可以用动态规划优化到 O(n) 时间 O(1) 空间。" 然后追问"如果每次可以爬 1 步、2 步或 3 步呢？"答案是 f(n) = f(n-1) + f(n-2) + f(n-3)。这种举一反三是面试官最想看到的。
3最大子序和 (Max Subarray) Medium
题目（人话版）
给你一个数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，找出一个连续的子数组，让它的和最大。答案是 [4, -1, 2, 1]，和为 6。
💡 生活类比：想象你在记录每天的收支：亏 2、赚 1、亏 3、赚 4、亏 1、赚 2、赚 1、亏 5、赚 4。你想知道连续哪几天的净利润最大。关键决策是：前面的累计利润如果是负数，就干脆"清零重来"——因为带着亏损走不如从头开始。
思路：Kadane 算法（动态规划的简化版）
遍历每个数
→
前面的累计和 < 0？
→
丢掉！从当前重新开始
否则
→
当前数 = 前面累计 + 当前数
→
更新最大值
maxSubarray.js
function maxSubArray(nums) {
let currSum = nums[0]; // 当前累计和
let maxSum = nums[0]; // 全局最大和
for (let i = 1; i < nums.length; i++) {
// 前面累计是负数？丢掉！从当前数重新开始
currSum = Math.max(nums[i], currSum + nums[i]);
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
模拟过程：[-2, 1, -3, 4, -1, 2, 1, -5, 4]
| i | 当前数 | 前面累计 | 决策 | currSum | maxSum |
|---|
| 0 | -2 | - | 初始 | -2 | -2 |
| 1 | 1 | -2 | -2<0，丢掉，从1开始 | 1 | 1 |
| 2 | -3 | 1 | 1>0，加上-3 | -2 | 1 |
| 3 | 4 | -2 | -2<0，丢掉，从4开始 | 4 | 4 |
| 4 | -1 | 4 | 4>0，加上-1 | 3 | 4 |
| 5 | 2 | 3 | 3>0，加上2 | 5 | 5 |
| 6 | 1 | 5 | 5>0，加上1 | 6 | 6 |
| 7 | -5 | 6 | 6>0，加上-5 | 1 | 6 |
| 8 | 4 | 1 | 1>0，加上4 | 5 | 6 |
时间 O(n)，空间 O(1)。一次遍历，只用了两个变量。
核心思想：Kadane 算法的精髓就一句话——"前面的累计如果是负数，那带着它走还不如丢掉重来"。这个贪心策略能保证每一步的 currSum 都是"以当前位置结尾的最大子序和"。
📋 动态规划专题速查表
| # | 题目 | 难度 |
|---|
| 1 | 斐波那契数列 (Fibonacci) | Easy |
| 2 | 爬楼梯 (Climbing Stairs) | Easy |
| 3 | 最大子序和 (Max Subarray) | Medium |
考点核心：动态规划专题的核心就是"用对工具，降复杂度"。
面试时拿到题先想："这道题能用动态规划吗？"
如果能，先说思路再写代码，面试官就知道你的分析能力。
🔗 其他考点专题
→ 双指针专题：回文检测 (Valid Palindrome), 反转字符串 (Reverse String), 合并两个有序数组 (Merge Sorted Arrays), 移动零 (Move Zeroes)
→ 哈希表专题：两数之和 (Two Sum), 有效的字母异位词 (Valid Anagram), 数组去重/判断有重复 (Contains Duplicate), 第一个唯一字符 (First Unique Character)
→ 位运算专题：只出现一次的数字 (Single Number), 缺失数字 (Missing Number)
→ 栈与滑动窗口专题：有效括号 (Valid Parentheses), 最长不重复子串 (Longest Substring)
→ 综合技巧专题：FizzBuzz, 买卖股票的最佳时机 (Best Time to Buy/Sell Stock), 多数元素 (Majority Element), 旋转数组 (Rotate Array), 二分查找 (Binary Search)
← 返回图解算法与模式