当代财经网

动态规划到底是什么？把大问题拆成小问题，别再死记递推公式

2026-09-18 14:24:43 米娜财富网

刷算法题最劝退的，八成有动态规划——名字听着像“动态改来改去”，其实核心思想就一句话：把复杂问题拆成重复子问题，记住答案，避免重复计算。它不是什么高深数学，而是一种“聪明地偷懒”的算法思想。

先搞懂两个关键词

状态：描述问题“到哪一步了”。比如“背包还剩多少容量”“字符串匹配到第几位”。

状态转移方程：当前状态如何从之前的状态推出来。这是动态规划的灵魂，相当于“递推公式”。

经典入门：斐波那契数列

用递归算第 n 个斐波那契数，会重复算很多次 F(2)、F(3)。动态规划的做法是：从 F(1)、F(2) 开始，一路算到 F(n)，把中间结果存进数组 dp[]，需要的时候直接查表——时间复杂度从指数级降到 O(n)。这就是最朴素的 DP。

三大特征，缺一不可

一个问题能用动态规划解决，通常要满足：

最优子结构：大问题的最优解，包含子问题的最优解(比如“最短路径”的子路径也是最短的);

重叠子问题：递归过程中，同一个子问题会被反复计算(斐波那契就是典型);

无后效性：当前状态一旦确定，后面的决策只和当前状态有关，和怎么走到这个状态无关。

解题四步走(通用模板)

定义状态：dp[i] 或 dp[i][j] 表示什么?比如 dp[i] 表示“前 i 个物品的最大价值”;

写出状态转移方程：dp[i] = max(dp[i-1], dp[i-1]+value[i]);

初始化边界：dp[0] = 0，或者 dp[0][0] = 1;

确定计算顺序：自底向上填表，避免递归栈溢出。

最经典的例子：0-1 背包问题

有 n 个物品，每个有重量 w[i] 和价值 v[i]，背包容量 W，每个物品只能选一次，问最大价值。

状态：dp[i][j] 表示“前 i 个物品，背包容量 j 时的最大价值”;

转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);

含义：不选第 i 个物品，或者选第 i 个物品(前提是容量够)。

常见误区

死背方程，不理解含义;

状态定义太复杂，导致转移写不出来;

忽略边界初始化，结果全错;

以为 DP 只能用于算法竞赛——其实在工程里，路径规划、资源调度、股票买卖、字符串匹配都用到它。

一句话：动态规划=用“状态+转移方程”把大问题拆小、把重复计算存起来，是算法里“用空间换时间”的典型代表。入门先啃透背包问题，再碰最长公共子序列、股票买卖，慢慢就通了。

推荐要闻
房产推荐
理财图文