代码随想录 — 动态规划与单调栈

对应 leetcode-master：动态规划理论基础、背包、打家劫舍、股票、子序列、回文、编辑距离、739/496/503/42/84 等。

---

一、动态规划理论基础

• 与贪心区别：DP 的当前状态由前一状态推导；贪心是每步局部最优，无状态推导。
• 解题五步（非常重要）：
  1. dp 数组及下标含义 — 想清楚 dp[i] 代表什么。
  2. 递推公式 — 如何从 dp 前面项得到当前项。
  3. 初始化 — 由递推和题意确定，有时递推公式决定初始化方式。
  4. 遍历顺序 — 保证计算当前状态时依赖的状态已算过；背包问题中顺序还会影响「选几次」。
  5. 举例推导 dp — 手推小样例，避免写错；Debug 时打印 dp 表对比。

Debug：先手推一遍 dp，再写代码；出错时打印 dp 数组，看是否与手推一致，再查递推/初始化/顺序。

---

二、背包问题（必掌握）

01 背包（每个最多选一次）

• 状态：dp[j] = 容量为 j 的背包能装的最大价值（一维时 j 从大到小遍历，避免同一物品用多次）。
• 递推：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])。
• 遍历：先遍历物品，再遍历容量（容量逆序）。

应用：416 分割等和子集（容量=和的一半）、494 目标和（正负号分组转化为背包）、1049 最后一块石头 II、474 一和零（二维费用）。

完全背包（每个可选多次）

• 一维：容量 从小到大 遍历，这样同一物品可重复选。
• 应用：518 零钱兑换 II（组合数）、377 组合总和 IV（排列数，先遍历容量再遍历物品）、322 零钱兑换（最少硬币数）、279 完全平方数、139 单词拆分。

多重背包

• 可拆成多个 01 背包或二进制优化；思路了解即可。

---

三、打家劫舍与股票

题目	思路要点
198 打家劫舍	dp[i] = max(dp[i-1], dp[i-2]+nums[i])，不能相邻。
213 打家劫舍 II	环：分「不偷第一家」和「不偷最后一家」两种线性做，取 max。
337 打家劫舍 III	树形 DP：返回 [不偷当前的最大, 偷当前的最大]；当前偷则左右都不能偷，当前不偷则左右取各自 max 相加。
121 买卖股票（一次）	记录「至今最低价」和「至今最大利润」；或 dp[i][0] 持有、dp[i][1] 不持有。
122/123/188	多笔：状态加「已交易次数」；123 最多 2 笔、188 最多 k 笔，注意 k 很大时退化成无限次。
309 含冷冻期	状态：持有、不持有（今天卖）、不持有（冷冻）；由前一天状态转移。
714 含手续费	在卖出时减 fee 即可。

---

四、子序列与子串

类型	代表题	思路要点
递增子序列	300 最长递增子序列	dp[i] 以 i 结尾的 LIS 长度；枚举 j<i 若 nums[j]<nums[i] 则 dp[i]=max(dp[i], dp[j]+1)。
公共/重复	718 最长重复子数组、1143 最长公共子序列	718 连续：dp[i][j] 以 A[i-1]、B[j-1] 结尾的最长公共前缀；1143 不要求连续：相等则 dp[i-1][j-1]+1，否则 max(dp[i-1][j], dp[i][j-1])。
最大和	53 最大子序和	dp[i]=nums[i]+max(0, dp[i-1])；或贪心。
编辑距离	72 编辑距离	dp[i][j] 表 s1[0..i) 到 s2[0..j) 最少操作；插入/删除/替换三种转移。
回文	647 回文子串、516 最长回文子序列	647：中心扩展或 dp[i][j] 表 [i,j] 是否回文，由 dp[i+1][j-1] 与 s[i]==s[j] 推；516：不连续，若 s[i]==s[j] 则 2+dp[i+1][j-1]，否则 max(dp[i+1][j], dp[i][j-1])。

---

五、其它经典 DP

• 70 爬楼梯：dp[i]=dp[i-1]+dp[i-2]。
• 746 最小花费爬楼梯：从 i 出发的最小花费，由 i-1 或 i-2 转移。
• 62/63 不同路径：dp[i][j]=dp[i-1][j]+dp[i][j-1]，有障碍则该格为 0。
• 343 整数拆分：dp[i] 为 i 拆成至少两个正整数的最大乘积；枚举第一段长度。
• 96 不同 BST：dp[n] 为 1..n 能构成的 BST 个数；枚举根 k，左子树 dp[k-1]，右子树 dp[n-k]。
• 32 最长有效括号：dp[i] 以 i 结尾的最长有效长度；若 s[i]==')' 且前面有匹配的 '(' 则从 dp[i-2] 或 dp[i-dp[i-1]-2] 转移。

---

六、单调栈

• 作用：通常求「每个元素左边/右边第一个比它大/小的元素」。
• 739 每日温度：找每个位置右边第一个更大。维护单调递减栈（存下标）；当前 T[i] 大于栈顶对应温度则栈顶的「下一个更大」就是 i，弹出并记录，直到栈空或栈顶更大，再压入 i。
• 496 下一个更大元素 I：先对 nums2 用单调栈得到「每个元素的下一个更大」，再在结果里按 nums1 取值。
• 503 下一个更大 II：数组视为循环，可把数组复制一份接在后面，或下标取模，同样单调栈。
• 42 接雨水：可单调栈（按「当前比栈顶高就形成洼地」算面积）；也可双指针/DP 记录左右最大高度。
• 84 柱状图最大矩形：对每个高度，找左右第一个比它小的位置，则宽为 (r-l-1)，面积为 height*宽；单调递增栈（存下标），弹栈时栈顶的右边界即当前 i，左边界即新栈顶。

小结：求「下一个更大」用单调减栈；求「下一个更小」用单调增栈；弹栈时即得到栈顶元素对应的答案。

---

七、DP 与单调栈总结

• DP：五步曲（含义、递推、初始化、顺序、手推）；01 背包一维逆序、完全背包一维正序；子序列注意连续/不连续、单串/双串。
• 单调栈：想清楚「栈内维护什么单调性」「弹栈时在算什么」；边界与空栈要处理清楚。

---

附：核心代码模板

01 背包（一维）

// JavaScript — 容量 bagSize，物品 weights/values
function knapsack01(weights, values, bagSize) {
  const dp = new Array(bagSize + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let j = bagSize; j >= weights[i]; j--) { // 逆序！
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }
  return dp[bagSize];
}

完全背包（一维）

// JavaScript — 每个物品可选多次
function knapsackComplete(weights, values, bagSize) {
  const dp = new Array(bagSize + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let j = weights[i]; j <= bagSize; j++) { // 正序！
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }
  return dp[bagSize];
}

最长递增子序列（300）

// JavaScript — 时间 O(n²)
function lengthOfLIS(nums) {
  const dp = new Array(nums.length).fill(1);
  let res = 1;
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    res = Math.max(res, dp[i]);
  }
  return res;
}

# Python — 最长公共子序列（1143）— 时间 O(mn)
def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

单调栈 — 每日温度（739）

// JavaScript — 时间 O(n)
function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const res = new Array(n).fill(0);
  const stack = []; // 存下标，栈内对应温度单调递减
  for (let i = 0; i < n; i++) {
    while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const top = stack.pop();
      res[top] = i - top;
    }
    stack.push(i);
  }
  return res;
}