Skip to content

动态规划

一句话解释

动态规划通过把复杂问题拆成重叠子问题并缓存其结果来求解。

用大白话说

动态规划(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)。

相关术语

相关资源

相关课程

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回术语表