动态规划

🧩 动态规划

动态规划 = 记忆化递归 = 用空间换时间。

🧩动态规划

斐波那契数列爬楼梯0-1 背包

斐波那契数列

时间 O(n)空间 O(n) 或 O(1)

第 n 个斐波那契数

dp[i] = dp[i-1] + dp[i-2]

n =8

速度:

▶️ 开始🔄 重置

DP 表格:

💡 动态规划核心

1. 定义状态

dp[i] 代表什么？

2. 状态转移

dp[i] 如何从 dp[i-1] 推导？

3. 基线条件

dp[0], dp[1] 初始值是什么？

---

🎯 核心三步

1. 定义状态

明确 dp[i] 代表什么：

• 斐波那契: dp[i] = 第 i 个斐波那契数
• 爬楼梯: dp[i] = 到第 i 阶的方法数
• 背包: dp[i][w] = 前 i 个物品、容量 w 的最大价值

2. 状态转移方程

如何从已知状态推导新状态：

// 斐波那契 / 爬楼梯
dp[i] = dp[i-1] + dp[i-2]

// 0-1 背包
dp[i][w] = max(
  dp[i-1][w],                    // 不选第 i 个物品
  dp[i-1][w-weight[i]] + value[i] // 选第 i 个物品
)

3. 基线条件

递推的起点：

dp[0] = 0;  // 或 1，取决于问题
dp[1] = 1;

---

📊 经典问题

1. 斐波那契数列

function fib(n) {
  if (n <= 1) return n;

  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}
// 时间 O(n), 空间 O(n)

// 空间优化版
function fibOptimized(n) {
  if (n <= 1) return n;

  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}
// 时间 O(n), 空间 O(1)

2. 爬楼梯 (LeetCode #70)

function climbStairs(n) {
  if (n <= 2) return n;

  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

3. 0-1 背包

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array(n + 1).fill(null)
    .map(() => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    const w = weights[i-1];
    const v = values[i-1];

    for (let c = 0; c <= capacity; c++) {
      if (w > c) {
        dp[i][c] = dp[i-1][c]; // 装不下
      } else {
        dp[i][c] = Math.max(
          dp[i-1][c],         // 不装
          dp[i-1][c-w] + v    // 装
        );
      }
    }
  }
  return dp[n][capacity];
}
// 时间 O(n×W), 空间 O(n×W)

---

💡 DP vs 贪心 vs 回溯

方法	特点	适用
DP	记录所有子问题	最优子结构 + 重叠子问题
贪心	只取局部最优	贪心选择性质
回溯	穷举 + 剪枝	组合/排列问题

---

🔗 相关知识

• 递归 - DP 的前身
• 复杂度分析 - 理解 O(n) vs O(2ⁿ)