您的位置：首页>科技 >

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

来源：米娜财富网时间：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 只能用于算法竞赛——其实在工程里，路径规划、资源调度、股票买卖、字符串匹配都用到它。

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

关键词：动态规划、动态规划解题步骤、DP状态转移方程、背包问题入门

财经热图

四川睿迪机电设备有限公司成立注册资本100万人民币-速看料

【涨停直击】终止收购液冷资产，祥鑫科技直线涨停|简讯

华阳集团主营哪些核心业务？华阳集团有哪些行业竞争优势？

慈禧太后经历哪些关键时期？慈禧太后带来哪些历史影响？

国际医学有什么核心医疗资源？国际医学行业发展优势在哪？

社保卡和医保卡是一张卡吗？社保卡和医保卡功能有区别吗？

gbp是什么货币全称？gbp货币有什么使用特点？

康恩贝有什么品牌核心优势？康恩贝未来发展潜力如何？

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

相关阅读

推荐阅读

塔县在新疆哪里？帕米尔高原上的“一县邻三国”边

龟兹国是现在的哪里？读音qiū cí，不是guī z

菜籽油的功效与作用有哪些？高烟点护心脑，但芥酸

平面轴承是干什么的？承轴向力还让部件转得顺，汽

网络知识入门先学什么？IP、DNS、路由懂了，WiFi

红酸枝是红木吗？交趾黄檀叫大红酸枝，别把“非洲

审计公司是干什么的？和内部审计、四大、代账公司

英寸转换厘米怎么算？1英寸=2.54厘米，记住这个数

财经热图