一、动态规划：从直觉到套路

动态规划，简称 DP。很多同学一听到这个词就头大。

说实话，我刚开始学的时候也一样。什么「最优子结构」、「重叠子问题」，听着就像天书。直到后来我在项目中真正用 DP 解决了一个调度优化问题，才恍然大悟——原来它没那么玄乎。

动态规划的核心思想，说白了就一句话：把大问题拆成小问题，记住小问题的答案，避免重复计算。

你想想看，这和我们平时做事是不是很像？比如你要从北京去上海，你不会每天重新规划路线，而是记住昨天走的那条路最快，今天接着用。

1.1 状态定义：一切的基础

状态定义是 DP 里最重要的一步。我个人习惯先问自己一个问题：「我到底需要记住哪些信息，才能推导出下一步？」

比如斐波那契数列，我需要知道第 n 项的值。那状态就可以定义为：dp[n] 表示第 n 个斐波那契数。

再比如爬楼梯问题，我需要知道爬到第 n 阶有多少种方法。状态就是：dp[n] 表示爬到第 n 阶的方法数。

1.2 状态转移方程：DP 的灵魂

状态转移方程，就是告诉你「怎么从已知推出未知」。它是 DP 的核心，也是最考验逻辑的地方。

拿斐波那契来说：

dp[0] = 0
dp[1] = 1
dp[n] = dp[n-1] + dp[n-2]   // n >= 2

这个方程的意思是：第 n 项等于前两项之和。很简单对吧？

爬楼梯问题其实一模一样：

dp[1] = 1
dp[2] = 2
dp[n] = dp[n-1] + dp[n-2]   // n >= 3

为什么？因为要爬到第 n 阶，你只能从第 n-1 阶跨一步上来，或者从第 n-2 阶跨两步上来。所以方法数就是这两种情况之和。

1.3 经典例题：斐波那契数列

斐波那契数列是 DP 的「Hello World」。咱们直接看代码：

// 递归版本（不推荐，有大量重复计算）
function fib(n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

// DP 版本（推荐）
function fibDP(n) {
    if (n <= 1) return n;
    let dp = new Array(n+1);
    dp[0] = 0;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// 空间优化版本（面试最爱）
function fibOptimized(n) {
    if (n <= 1) return n;
    let prev2 = 0, prev1 = 1;
    for (let i = 2; i <= n; i++) {
        let curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

你看，从递归到 DP 再到空间优化，一步步在改进。递归版本的时间复杂度是 O(2^n)，DP 版本是 O(n)，空间优化版本不仅时间 O(n)，空间也降到了 O(1)。

1.4 经典例题：爬楼梯

爬楼梯问题，其实就是斐波那契的变种。但它的实际意义更强——很多实际问题都能抽象成爬楼梯。

// 标准 DP
function climbStairs(n) {
    if (n <= 2) return n;
    let dp = new Array(n+1);
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// 空间优化
function climbStairsOptimized(n) {
    if (n <= 2) return n;
    let prev2 = 1, prev1 = 2;
    for (let i = 3; i <= n; i++) {
        let curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

1.5 DP 核心思想总结

说了这么多，咱们来张图总结一下 DP 的核心流程：

1.6 什么时候用 DP？

不是所有问题都能用 DP。我个人总结了三个判断标准：

特征	说明	例子
最优子结构	大问题的最优解包含子问题的最优解	爬楼梯：到第 n 阶的方法由前两阶决定
重叠子问题	子问题会被重复计算多次	斐波那契：fib(5) 会多次计算 fib(3)
无后效性	子问题的解一旦确定，不受后续决策影响	背包问题：选或不选，不影响之前的选择

嗯，这一章的内容就到这。斐波那契和爬楼梯是 DP 的入门砖，别看它们简单，背后的思想贯穿了整个 DP 体系。下一章我们会聊更复杂的「路径问题」，到时候你会发现——套路其实都一样。

---

公众号:蓝海资料掘金营，微信deep3321