动态规划专题

动态规划核心：定义状态 + 状态转移方程 + 边界条件

📊 题目总览

题目	难度	梯队	关键技巧
爬楼梯	⭐⭐	第一梯队	基础 DP
零钱兑换	⭐⭐	第二梯队	完全背包
最长递增子序列	⭐⭐⭐	第二梯队	LIS
最长公共子序列	⭐⭐⭐	第三梯队	LCS
0-1 背包问题	⭐⭐⭐	第三梯队	经典背包
打家劫舍	⭐⭐	第二梯队	状态选择

DP 核心思想

适用条件

最优子结构: 问题的最优解包含子问题的最优解
重叠子问题: 相同子问题被反复计算

解题步骤

1. 定义状态：dp[i] 的含义是什么
2. 状态转移方程：dp[i] 如何由之前的状态推导
3. 初始化边界：dp[0] 或 dp[0][0] 等初始值
4. 遍历顺序：从小到大还是从大到小
5. 空间优化：滚动数组降低空间复杂度

1. 爬楼梯

LeetCode: 70. 爬楼梯 | 难度: 简单 | 梯队: 第一梯队 ✅

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

输入: n = 3
输出: 3
解释: 有三种方法: 1+1+1, 1+2, 2+1

核心思路

状态定义: dp[i] = 爬到第 i 阶的方法数
状态转移: dp[i] = dp[i-1] + dp[i-2]（从 i-1 爬 1 阶，或从 i-2 爬 2 阶）
边界条件: dp[1] = 1, dp[2] = 2

代码实现

javascript

/**
 * 爬楼梯 - 空间优化版
 * @param {number} n
 * @return {number}
 */
function climbStairs(n) {
  if (n <= 2) return n;

  let prev1 = 1; // dp[i-2]
  let prev2 = 2; // dp[i-1]

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

  return prev2;
}

/**
 * 爬楼梯 - 标准 DP 版（易理解）
 * @param {number} n
 * @return {number}
 */
function climbStairsDP(n) {
  if (n <= 2) return n;

  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;

  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

示例调用

javascript

// 基础示例
console.log(climbStairs(3)); // 3
console.log(climbStairs(4)); // 5
console.log(climbStairs(5)); // 8

// 边界条件：最小值
console.log(climbStairs(1)); // 1
console.log(climbStairs(2)); // 2

// 边界条件：较大值
console.log(climbStairs(10)); // 89
console.log(climbStairs(45)); // 1836311903

复杂度分析

时间: O(n)
空间: O(1)（优化版）/ O(n)（标准版）

2. 零钱兑换

LeetCode: 322. 零钱兑换 | 难度: 中等 | 梯队: 第二梯队

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。计算可以凑成总金额所需的最少硬币个数。如果无法凑成，返回 -1。

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

核心思路

状态定义: dp[i] = 凑成金额 i 所需的最少硬币数
状态转移: dp[i] = min(dp[i], dp[i - coin] + 1) 对每个硬币
边界条件: dp[0] = 0（凑成 0 元需要 0 个硬币）

代码实现

javascript

/**
 * 零钱兑换
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
function coinChange(coins, amount) {
  // 初始化为 amount + 1（不可能的值，相当于 Infinity）
  const dp = new Array(amount + 1).fill(amount + 1);
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i >= coin) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] > amount ? -1 : dp[amount];
}

/**
 * 零钱兑换 - 完全背包写法
 * 遍历顺序：先遍历硬币，再遍历金额
 */
function coinChangeKnapsack(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

示例调用

javascript

// 基础示例
console.log(coinChange([1, 2, 5], 11)); // 3 (5+5+1)
console.log(coinChange([2], 3));        // -1 (无法凑成)
console.log(coinChange([1], 0));        // 0 (金额为0不需要硬币)

// 边界条件：只有1元硬币
console.log(coinChange([1], 5));        // 5

// 边界条件：无法凑成
console.log(coinChange([2], 1));        // -1

// 边界条件：单个大面额硬币
console.log(coinChange([1, 2, 5], 5));  // 1

// 边界条件：需要多种组合
console.log(coinChange([1, 3, 5], 11)); // 3 (5+3+3)

// 边界条件：大金额
console.log(coinChange([1, 2, 5], 100)); // 20 (20个5元)

复杂度分析

时间: O(n × amount)，n 为硬币种类数
空间: O(amount)

3. 最长递增子序列

LeetCode: 300. 最长递增子序列 | 难度: 中等 | 梯队: 第二梯队

题目描述

给定一个整数数组 nums，找到其中最长严格递增子序列的长度。

输入: nums = [10, 9, 2, 5, 3, 7, 101, 18]
输出: 4
解释: 最长递增子序列是 [2, 3, 7, 101]

核心思路

方法一：动态规划 O(n²)

dp[i] = 以 nums[i] 结尾的 LIS 长度
对于每个 j < i，若 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)

方法二：二分查找 O(n log n)

维护一个递增数组 tails，tails[i] 表示长度为 i+1 的 LIS 的最小结尾元素
对于每个数，二分查找其位置并更新

代码实现

javascript

/**
 * 最长递增子序列 - DP 解法
 * @param {number[]} nums
 * @return {number}
 */
function lengthOfLIS(nums) {
  if (!nums.length) return 0;

  const dp = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

/**
 * 最长递增子序列 - 二分优化（推荐）
 * @param {number[]} nums
 * @return {number}
 */
function lengthOfLISBinary(nums) {
  if (!nums.length) return 0;

  const tails = [nums[0]];

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > tails[tails.length - 1]) {
      // 比所有元素都大，直接追加
      tails.push(nums[i]);
    } else {
      // 二分查找第一个 >= nums[i] 的位置并替换
      let left = 0, right = tails.length - 1;
      while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        if (tails[mid] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      tails[left] = nums[i];
    }
  }

  return tails.length;
}

示例调用

javascript

// 基础示例
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4

// 全递增
console.log(lengthOfLIS([1, 2, 3, 4, 5])); // 5

// 全递减
console.log(lengthOfLIS([5, 4, 3, 2, 1])); // 1

// 边界条件：空数组
console.log(lengthOfLIS([])); // 0

// 边界条件：单个元素
console.log(lengthOfLIS([1])); // 1

// 边界条件：有重复元素
console.log(lengthOfLIS([1, 3, 6, 7, 9, 4, 10, 5, 6])); // 6

// 边界条件：全部相等
console.log(lengthOfLIS([7, 7, 7, 7, 7])); // 1 (严格递增)

复杂度分析

方法	时间复杂度	空间复杂度
DP	O(n²)	O(n)
二分优化	O(n log n)	O(n)

4. 最长公共子序列

LeetCode: 1143. 最长公共子序列 | 难度: 中等 | 梯队: 第三梯队

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

输入: text1 = "abcde", text2 = "ace"
输出: 3
解释: 最长公共子序列是 "ace"

核心思路

状态定义: dp[i][j] = text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度
状态转移:
- 若 text1[i-1] === text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
- 否则: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
边界条件: dp[0][j] = dp[i][0] = 0

代码实现

javascript

/**
 * 最长公共子序列
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;

  // dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

/**
 * 空间优化版本 - 滚动数组
 */
function longestCommonSubsequenceOptimized(text1, text2) {
  const m = text1.length;
  const n = text2.length;

  // 只保留两行
  let prev = new Array(n + 1).fill(0);
  let curr = new Array(n + 1).fill(0);

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        curr[j] = prev[j - 1] + 1;
      } else {
        curr[j] = Math.max(prev[j], curr[j - 1]);
      }
    }
    [prev, curr] = [curr, prev];
  }

  return prev[n];
}

示例调用

javascript

// 基础示例
console.log(longestCommonSubsequence("abcde", "ace")); // 3 ("ace")
console.log(longestCommonSubsequence("abc", "abc"));   // 3
console.log(longestCommonSubsequence("abc", "def"));   // 0

// 边界条件：空字符串
console.log(longestCommonSubsequence("", "abc"));      // 0
console.log(longestCommonSubsequence("abc", ""));      // 0
console.log(longestCommonSubsequence("", ""));         // 0

// 边界条件：单字符
console.log(longestCommonSubsequence("a", "a"));       // 1
console.log(longestCommonSubsequence("a", "b"));       // 0

// 边界条件：一个是另一个的子序列
console.log(longestCommonSubsequence("ace", "abcde")); // 3

// 边界条件：有重复字符
console.log(longestCommonSubsequence("aaa", "aa"));    // 2
console.log(longestCommonSubsequence("abab", "baba")); // 3

复杂度分析

时间: O(m × n)
空间: O(m × n) / O(n) 优化后

5. 0-1 背包问题

经典问题 | 难度: 中等 | 梯队: 第三梯队

题目描述

有 n 个物品，每个物品有重量 weights[i] 和价值 values[i]。背包最大承重为 capacity。每个物品只能选一次，求能装入背包的最大价值。

输入: weights = [1, 2, 3], values = [6, 10, 12], capacity = 5
输出: 22
解释: 选择物品 0 和物品 2 (重量 1+3=4, 价值 6+12=18)
      或选择物品 1 和物品 2 (重量 2+3=5, 价值 10+12=22)

核心思路

状态定义: dp[i][w] = 前 i 个物品，容量为 w 时的最大价值
状态转移:
- 不选第 i 个物品: dp[i][w] = dp[i-1][w]
- 选第 i 个物品: dp[i][w] = dp[i-1][w-weights[i]] + values[i]
- dp[i][w] = max(不选, 选)
空间优化: 一维数组，倒序遍历容量

代码实现

javascript

/**
 * 0-1 背包 - 二维 DP
 * @param {number[]} weights - 物品重量
 * @param {number[]} values - 物品价值
 * @param {number} capacity - 背包容量
 * @return {number}
 */
function knapsack01(weights, values, capacity) {
  const n = weights.length;
  // dp[i][w] = 前 i 个物品，容量 w 的最大价值
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      // 不选第 i 个物品
      dp[i][w] = dp[i - 1][w];
      // 选第 i 个物品（如果装得下）
      if (w >= weights[i - 1]) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        );
      }
    }
  }

  return dp[n][capacity];
}

/**
 * 0-1 背包 - 空间优化（一维）
 * 关键：必须倒序遍历容量，防止重复选取
 */
function knapsack01Optimized(weights, values, capacity) {
  const n = weights.length;
  const dp = new Array(capacity + 1).fill(0);

  for (let i = 0; i < n; i++) {
    // 必须倒序遍历！
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }

  return dp[capacity];
}

示例调用

javascript

// 基础示例
console.log(knapsack01([1, 2, 3], [6, 10, 12], 5)); // 22

// 边界条件：容量为 0
console.log(knapsack01([1, 2, 3], [6, 10, 12], 0)); // 0

// 边界条件：空物品列表
console.log(knapsack01([], [], 10)); // 0

// 边界条件：单个物品
console.log(knapsack01([5], [10], 5));  // 10
console.log(knapsack01([5], [10], 4));  // 0 (装不下)

// 边界条件：所有物品都装不下
console.log(knapsack01([10, 20, 30], [1, 2, 3], 5)); // 0

// 边界条件：刚好装满
console.log(knapsack01([2, 3], [10, 15], 5)); // 25

// 边界条件：容量很大
console.log(knapsack01([1, 2, 3], [6, 10, 12], 100)); // 28 (全选)

完全背包对比

javascript

/**
 * 完全背包 - 每个物品可以无限选
 * 区别：正序遍历容量
 */
function knapsackComplete(weights, values, capacity) {
  const n = weights.length;
  const dp = new Array(capacity + 1).fill(0);

  for (let i = 0; i < n; i++) {
    // 正序遍历，允许重复选取
    for (let w = weights[i]; w <= capacity; w++) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }

  return dp[capacity];
}

// 对比示例
console.log(knapsack01([1, 2, 3], [6, 10, 12], 5));       // 22 (0-1背包)
console.log(knapsackComplete([1, 2, 3], [6, 10, 12], 5)); // 30 (完全背包: 5个物品0)

复杂度分析

时间: O(n × capacity)
空间: O(capacity) 优化后

6. 打家劫舍

LeetCode: 198. 打家劫舍 | 难度: 中等 | 梯队: 第二梯队

题目描述

你是一个小偷，沿街房屋存有现金。相邻房屋装有报警器，如果两间相邻房屋在同一晚被闯入，系统会报警。求在不触动警报的情况下，能偷窃到的最高金额。

输入: [1, 2, 3, 1]
输出: 4
解释: 偷窃 1 号房 (金额 = 1) 和 3 号房 (金额 = 3)，总金额 = 4

核心思路

状态定义: dp[i] = 偷到第 i 个房屋时的最大金额
状态转移:
- 偷第 i 个: dp[i-2] + nums[i]
- 不偷第 i 个: dp[i-1]
- dp[i] = max(dp[i-1], dp[i-2] + nums[i])
空间优化: 只需保留前两个状态

代码实现

javascript

/**
 * 打家劫舍
 * @param {number[]} nums
 * @return {number}
 */
function rob(nums) {
  if (!nums.length) return 0;
  if (nums.length === 1) return nums[0];

  let prev1 = 0;        // dp[i-2]
  let prev2 = nums[0];  // dp[i-1]

  for (let i = 1; i < nums.length; i++) {
    const curr = Math.max(prev2, prev1 + nums[i]);
    prev1 = prev2;
    prev2 = curr;
  }

  return prev2;
}

/**
 * 打家劫舍 II - 环形版（房屋围成一圈）
 * LeetCode 213
 */
function robCircular(nums) {
  if (!nums.length) return 0;
  if (nums.length === 1) return nums[0];

  // 偷第一个，不偷最后一个
  const rob1 = robRange(nums, 0, nums.length - 2);
  // 不偷第一个，偷最后一个
  const rob2 = robRange(nums, 1, nums.length - 1);

  return Math.max(rob1, rob2);
}

function robRange(nums, start, end) {
  let prev1 = 0;
  let prev2 = 0;

  for (let i = start; i <= end; i++) {
    const curr = Math.max(prev2, prev1 + nums[i]);
    prev1 = prev2;
    prev2 = curr;
  }

  return prev2;
}

/**
 * 打家劫舍 III - 树形版
 * LeetCode 337
 */
function robTree(root) {
  function dfs(node) {
    if (!node) return [0, 0]; // [不选当前, 选当前]

    const left = dfs(node.left);
    const right = dfs(node.right);

    // 不选当前节点：子节点可选可不选，取最大
    const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    // 选当前节点：子节点必须不选
    const doRob = node.val + left[0] + right[0];

    return [notRob, doRob];
  }

  const [notRob, doRob] = dfs(root);
  return Math.max(notRob, doRob);
}

示例调用

javascript

// 基础示例
console.log(rob([1, 2, 3, 1])); // 4
console.log(rob([2, 7, 9, 3, 1])); // 12 (2+9+1)

// 边界条件：空数组
console.log(rob([])); // 0

// 边界条件：单个元素
console.log(rob([5])); // 5

// 边界条件：两个元素
console.log(rob([2, 3])); // 3

// 边界条件：全部相等
console.log(rob([5, 5, 5, 5])); // 10

// 边界条件：递增
console.log(rob([1, 2, 3, 4, 5])); // 9 (1+3+5)

// 环形版本
console.log(robCircular([2, 3, 2])); // 3
console.log(robCircular([1, 2, 3, 1])); // 4
console.log(robCircular([1, 2, 3])); // 3

复杂度分析

版本	时间复杂度	空间复杂度
基础版	O(n)	O(1)
环形版	O(n)	O(1)
树形版	O(n)	O(h) 递归栈

💡 动态规划技巧总结

DP 问题分类

类型	典型题目	特点
线性 DP	爬楼梯、打家劫舍	单数组，一维状态
背包 DP	0-1 背包、零钱兑换	选择问题
双序列 DP	LCS、编辑距离	两个字符串
区间 DP	戳气球、矩阵链乘法	区间划分
状态压缩 DP	TSP、棋盘覆盖	状态用二进制表示
树形 DP	打家劫舍 III	在树上做 DP

解题模板

javascript

// 通用 DP 模板
function dpSolution(input) {
  const n = input.length;

  // 1. 定义状态
  const dp = new Array(n + 1).fill(初始值);

  // 2. 边界条件
  dp[0] = 边界值;

  // 3. 状态转移
  for (let i = 1; i <= n; i++) {
    dp[i] = 状态转移方程(dp[i-1], input[i-1], ...);
  }

  // 4. 返回结果
  return dp[n]; // 或 Math.max(...dp)
}

空间优化技巧

javascript

// 优化前：二维数组
const dp = Array.from({ length: m }, () => new Array(n).fill(0));

// 优化后：滚动数组（两行）
let prev = new Array(n).fill(0);
let curr = new Array(n).fill(0);
// 循环后交换 [prev, curr] = [curr, prev]

// 优化后：一维数组（注意遍历顺序）
const dp = new Array(n).fill(0);
// 0-1 背包：倒序遍历
// 完全背包：正序遍历

动态规划专题 ​

📊 题目总览 ​

DP 核心思想 ​

适用条件 ​

解题步骤 ​

1. 爬楼梯 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

2. 零钱兑换 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

3. 最长递增子序列 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

4. 最长公共子序列 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

5. 0-1 背包问题 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

完全背包对比 ​

复杂度分析 ​

6. 打家劫舍 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

💡 动态规划技巧总结 ​

DP 问题分类 ​

解题模板 ​

空间优化技巧 ​

动态规划专题

📊 题目总览

DP 核心思想

适用条件

解题步骤

1. 爬楼梯

题目描述

核心思路

代码实现

示例调用

复杂度分析

2. 零钱兑换

题目描述

核心思路

代码实现

示例调用

复杂度分析

3. 最长递增子序列

题目描述

核心思路

代码实现

示例调用

复杂度分析

4. 最长公共子序列

题目描述

核心思路

代码实现

示例调用

复杂度分析

5. 0-1 背包问题

题目描述

核心思路

代码实现

示例调用

完全背包对比

复杂度分析

6. 打家劫舍

题目描述

核心思路

代码实现

示例调用

复杂度分析

💡 动态规划技巧总结

DP 问题分类

解题模板

空间优化技巧