动态规划入门：核心思想与实战应用

说实话，动态规划（DP）是我在算法学习路上遇到的第一个真正意义上的「分水岭」。

很多人觉得它玄乎，其实说白了，DP 就是一种聪明的穷举——把大问题拆成小问题，记住小问题的答案，避免重复计算。嗯，就这么简单。

核心思想：记住过去，复用未来

动态规划的核心就八个字：「以空间换时间」。

你想想看，如果一个问题可以分解成相互重叠的子问题，那我们每次算完一个子问题，就把结果存起来。下次再遇到同样的子问题，直接查表，不用重新算。

我在项目中遇到过这样一个场景：做路径规划时，要反复计算某个节点到终点的最短距离。如果不做记忆化，每次都要重新遍历整张图，数据量一大直接超时。后来用 DP 表存起来，速度提升了上百倍。

重叠子问题：为什么 DP 能省时间？

重叠子问题是 DP 能提速的根本原因。

什么叫重叠？就是不同的「大问题」会共享同一个「小问题」。比如斐波那契数列，F(5) 需要 F(4) 和 F(3)，F(4) 又需要 F(3) 和 F(2)。你看，F(3) 被重复计算了两次。

如果不用 DP，递归树会指数级膨胀。用了 DP，每个子问题只算一次，复杂度从 O(2^n) 降到 O(n)。

最优子结构：局部最优能推出全局最优

最优子结构听起来高大上，其实意思很简单：大问题的最优解，可以由子问题的最优解推导出来。

举个例子，你要从北京到上海走最短路径。如果最优路径经过了济南，那么从北京到济南这一段，也一定是最短的。否则，你可以换一条更短的到济南的路，整体就更短了——这就矛盾了。

我曾经踩过一个坑：在某个资源分配问题里，我默认它有最优子结构，结果算出来的方案根本不对。后来发现，子问题之间会相互影响，不能独立求解。嗯，这里要注意——不是所有问题都有最优子结构。

与贪心的区别：一个短视，一个全局

很多初学者分不清 DP 和贪心。我建议你记住一句话：贪心是「走一步看一步」，DP 是「走一步看全局」。

对比维度	动态规划	贪心算法
决策方式	考虑所有可能，选最优	只选当前最优
子问题依赖	子问题之间有重叠	子问题通常独立
正确性	保证全局最优	不一定全局最优
典型问题	背包问题、最短路径	活动选择、哈夫曼编码

举个生活中的例子：你去自助餐厅，贪心是「先拿眼前最大的那块肉」，DP 是「先观察一圈，规划好怎么拿才能吃回本」。哪个更优？显然是 DP，但代价是你要多花时间观察。

斐波那契数列：DP 的 Hello World

斐波那契数列是理解 DP 最好的入门题。咱们先看最朴素的递归写法：

// 朴素递归 —— 指数级复杂度
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

这个写法的问题在哪？重复计算太多了。算 fib(5) 时，fib(3) 被算了两次，fib(2) 被算了三次。n 越大，重复越严重。

接下来，我们用记忆化搜索（自顶向下 DP）来优化：

// 记忆化搜索 —— O(n) 时间，O(n) 空间
int memo[100] = {0};

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];  // 查表
    memo[n] = fib(n-1) + fib(n-2);     // 存表
    return memo[n];
}

你看，只加了一个数组和一行判断，复杂度就从指数级降到了线性。这就是 DP 的魅力。

当然，我们还可以用自底向上的迭代写法：

// 自底向上 DP —— O(n) 时间，O(1) 空间
int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

这个版本连数组都省了，只用两个变量滚动更新。空间复杂度 O(1)，完美。

知识体系总览

下面这张图总结了本章的核心逻辑，我建议你多看几遍：

这张图把 DP 的核心脉络都串起来了。你从中心出发，左边是思想，中间是方法，右边是对比，底部是具体实现。学 DP 时，就按这个框架来，不容易乱。

---

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