【算法】小白也能懂 · 第 11 节：动态规划入门

在前面 10 节中，我们学了递归、二叉树、图的 BFS/DFS 等基础数据结构与算法。今天，我们来认识一个让无数初学者又爱又恨的概念——动态规划（Dynamic Programming，简称 DP）。别怕，跟着节奏走，你会发现它其实没那么神秘。1. 什么是动态规划简单来说，动态规划的核心思想就是一句话：把大问题拆成小问题，记住已经算过的结果，避免重复计算。你可以把 DP 想象成一个"聪明的备忘录"。比如你去餐厅点菜，第一次算总价很慢，但你把结果记在小本本上。下次有人问同样的组合，直接翻本子就行，不用重新算。DP 有两种经典写法：自顶向下（记忆化搜索）：从大问题出发，用递归拆解，同时用数组或哈希表记录已算过的结果。自底向上（递推）：从最小的子问题开始，逐步向上推导出最终答案。两种写法殊途同归，选择哪种看个人习惯和题目场景。2. DP 的两个关键性质一个能用 DP 解决的问题，通常具备两个特征：2.1 最优子结构大问题的最优解，可以由子问题的最优解组合得到。比如"从 A 到 C 的最短路径"，如果经过 B，那么 A 到 B 的部分一定也是最短的。2.2 重叠子问题递归过程中，同一个子问题会被反复计算。这就是 DP 存在的意义——把重复的计算结果缓存起来，只算一次。3. 经典例子 1：斐波那契数列斐波那契数列定义：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)。我们从朴素递归一步步优化到 DP。3.1 朴素递归（很慢）#includeiostreamusingnamespacestd;intfib(intn){if(n=1)returnn;returnfib(n-1)+fib(n-2);}intmain(){coutfib(10)endl;// 输出 55return0;}这段代码简单直观，但时间复杂度是 O(2^n)。为什么？因为fib(5)会算fib(4)和fib(3)，而fib(4)又会算fib(3)——fib(3)被算了两次！n 越大，重复越多，指数级爆炸。3.2 记忆化搜索（自顶向下 DP）加一个memo数组缓存结果，每个子问题只算一次，时间复杂度降为 O(n)！#includeiostream#includecstringusingnamespacestd;intmemo[100];intfib(intn){if(n=1)returnn;if(memo[n]!=-1)returnmemo[n];// 已算过，直接返回memo[n]=fib(n-1)+fib(n-2);returnmemo[n];