动态规划
一句话解释
动态规划通过把复杂问题拆成重叠子问题并缓存其结果来求解。
用大白话说
动态规划(DP)是一种求解具有重叠子问题和最优子结构问题的技术。你把问题拆成更小的片段,每片只解一次并存(记忆化)其结果,绝不重复计算。这能把指数级递归解法变成多项式级。经典例子是斐波那契:朴素递归会多次计算 fib(2)。加上记忆化后,每个 fib(n) 只算一次并缓存,把 O(2^n) 降为 O(n)。其他 DP 问题包括背包问题、最长公共子序列、编辑距离、找零钱。DP 可自顶向下(递归 + 记忆缓存)或自底向上(从小到大填表)实现。自底向上常用数组迭代,避免递归开销。难点在于识别状态与递推关系——一旦确定,代码通常很直接。
示例
javascript
// 带记忆化的斐波那契(自顶向下 DP)
const memo = {};
function fib(n) {
if (n <= 1) return n;
if (memo[n] !== undefined) return memo[n];
return memo[n] = fib(n - 1) + fib(n - 2);
}
console.log(fib(10)); // 55
console.log(fib(40)); // 102334155 — 因结果被缓存而很快每个 fib(n) 只计算一次并存入 memo。后续调用返回缓存值,把 O(2^n) 降为 O(n)。
相关术语
相关资源
相关课程
- 算法
学习动态规划。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。