文章

动态规划入门深度解析

发表于
作者 独行的风
21 分钟阅读
动态规划入门深度解析

一句话概括

动态规划（Dynamic Programming，简称 DP）是一种通过将复杂问题拆解为重叠子问题、并利用状态转移方程来高效求解的算法设计思想，本文从斐波那契数列出发，逐步深入到爬楼梯问题和背包问题，完整推导状态转移方程并用 JavaScript 实现。

背景与意义

动态规划是算法面试中的「重头戏」。据统计，在 LeetCode 高频面试题中，动态规划相关题目占比超过 20%。许多看似无从下手的问题——背包装什么最有价值、编辑两个字符串的最少操作次数、机器人走网格有多少条路径——在 DP 的框架下都能优雅地解决。

DP 核心思想可以浓缩为三个词：状态定义、状态转移、边界条件。这三个词贯穿所有 DP 问题。

DP 与分治的区别

分治也是「大事化小」，但分治的子问题彼此独立（如归并排序），DP 的子问题则高度重叠。正是这种重叠性质，让 DP 可以通过「备忘录」或「填表」的方式避免重复计算，从而指数级提升效率。

概念与定义

动态规划：通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划适用于有重叠子问题和最优子结构性质的问题。

重叠子问题：子问题之间不是独立的，一个子问题在求解过程中会被多次用到。

最优子结构：原问题的最优解可以通过子问题的最优解推导得出。

状态（State）：DP 表中每一个格子代表一个状态，表示在某个阶段下的最优值或方案数。

状态转移方程：描述状态之间关系的数学表达式，是 DP 问题的核心。

边界条件：最小的子问题的解，是状态转移的起点。

核心知识点拆解

1. 斐波那契数列：DP 的 Hello World

斐波那契数列看似简单，却完整展示了 DP 从「暴力递归」到「记忆化搜索」再到「自底向上 DP」的演进过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

/**
 * 方法一：暴力递归（无优化）
 * 时间复杂度：O(2^n) 空间复杂度：O(n)
 * 大量重复计算，n = 50 就慢到无法接受
 */
function fibBruteForce(n) {
  if (n <= 1) return n;
  return fibBruteForce(n - 1) + fibBruteForce(n - 2);
}

/**
 * 方法二：记忆化递归（自顶向下）
 * 时间复杂度：O(n) 空间复杂度：O(n)
 * 用数组缓存已计算的结果，避免重复计算
 */
function fibMemoization(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  
  memo[n] = fibMemoization(n - 1, memo) + fibMemoization(n - 2, memo);
  return memo[n];
}

/**
 * 方法三：自底向上 DP（迭代填表）
 * 时间复杂度：O(n) 空间复杂度：O(n)
 * DP 计算的经典形式
 */
function fibDP(n) {
  if (n <= 1) return n;
  
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

/**
 * 方法四：空间优化（滚动变量）
 * 时间复杂度：O(n) 空间复杂度：O(1)
 * 因为 dp[i] 只依赖前两个状态，无需保留整个数组
 */
function fibOptimized(n) {
  if (n <= 1) return n;
  
  let prev2 = 0; // dp[i-2]
  let prev1 = 1; // dp[i-1]
  
  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  
  return prev1;
}

状态转移方程：

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

边界条件：$dp[0] = 0, dp[1] = 1$

这是一个一维线性 DP 的典型案例。从最简单的问题入手，我们可以看到 DP 的四个进化阶段：

  1. 暴力递归（指数级）→ 认识到问题
  2. 记忆化递归（缓存子问题）→ 消除重复计算
  3. 自底向上填表（正向迭代）→ 最优子结构体现
  4. 空间压缩（滚动数组）→ 极致优化

2. 爬楼梯问题：不同路径的计数

爬楼梯是斐波那契的「亲兄弟」，但加入了对问题建模的思考步骤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/**
 * LeetCode 70 - 爬楼梯
 * 问题：每次可以爬 1 或 2 个台阶，爬到第 n 阶有多少种不同方法？
 * 
 * 状态定义：dp[i] 表示爬到第 i 阶的不同方法数
 * 状态转移：爬到第 i 阶可以从第 i-1 阶跨一步，或从第 i-2 阶跨两步
 * 所以：dp[i] = dp[i-1] + dp[i-2]
 * 边界：dp[1] = 1, dp[2] = 2
 * 实际上就是斐波那契数列！
 */
function climbStairs(n) {
  if (n <= 2) return n;
  
  let prev2 = 1; // dp[1]
  let prev1 = 2; // dp[2]
  
  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  
  return prev1;
}

/**
 * 爬楼梯变体：每次可以爬 1、2 或 3 步
 * 状态转移：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
 */
function climbStairsThreeSteps(n) {
  if (n <= 2) return n;
  if (n === 3) return 4;
  
  let prev3 = 1; // dp[1]
  let prev2 = 2; // dp[2]
  let prev1 = 4; // dp[3]
  
  for (let i = 4; i <= n; i++) {
    const current = prev1 + prev2 + prev3;
    prev3 = prev2;
    prev2 = prev1;
    prev1 = current;
  }
  
  return prev1;
}

爬楼梯问题揭示了一个重要规律：当状态转移仅依赖前 k 个状态时，可以将空间复杂度从 $O(n)$ 降到 $O(k)$。几乎所有一维 DP 都存在这种空间优化机会。

3. 背包问题：DP 的核心经典

背包问题（Knapsack）是 DP 入门的必修课，包含了 DP 所有核心要素：二维状态定义、选/不选的决策模型、空间压缩技巧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

/**
 * 0/1 背包问题
 * 问题：有 n 件物品，每件物品重量 w[i]，价值 v[i]，
 * 背包容量为 capacity，每件物品只能取一次，求最大价值
 *
 * 状态定义：dp[i][j] 表示前 i 件物品中选，容量为 j 时的最大价值
 * 状态转移：
 *   - 不选第 i 件：dp[i][j] = dp[i-1][j]
 *   - 选第 i 件：dp[i][j] = dp[i-1][j-w[i]] + v[i]
 *   - 取两者较大值
 * 边界：dp[0][j] = 0（没有物品时价值为 0）
 */
function knapsack01(weights, values, capacity) {
  const n = weights.length;
  // dp[i][j] 前 i 个物品，容量 j 的最大价值
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    const w = weights[i - 1];
    const v = values[i - 1];
    
    for (let j = 0; j <= capacity; j++) {
      if (j < w) {
        // 装不下，只能不选
        dp[i][j] = dp[i - 1][j];
      } else {
        // 能装下，取「不选」和「选」的最大值
        dp[i][j] = Math.max(
          dp[i - 1][j],              // 不选
          dp[i - 1][j - w] + v       // 选
        );
      }
    }
  }
  
  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++) {
    const w = weights[i];
    const v = values[i];
    
    // 从大到小遍历，确保 dp[j-w] 是上一轮的值
    for (let j = capacity; j >= w; j--) {
      dp[j] = Math.max(dp[j], dp[j - w] + v);
    }
  }
  
  return dp[capacity];
}

/**
 * 完全背包问题（每件物品可取无限次）
 * 与 0/1 背包的唯一区别：内层循环从小到大遍历
 * 因为允许重复选取，dp[j-w] 可以是本轮已更新的值
 */
function completeKnapsack(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  
  for (let i = 0; i < weights.length; i++) {
    const w = weights[i];
    const v = values[i];
    
    // 从小到大遍历 - 这是完全背包与 0/1 背包的核心区别
    for (let j = w; j <= capacity; j++) {
      dp[j] = Math.max(dp[j], dp[j - w] + v);
    }
  }
  
  return dp[capacity];
}

背包问题的思考模板：

  • 状态定义：dp[i][j] 前 i 个物品中选，容量为 j 的最优解
  • 决策：每个物品「选」或「不选」
  • 遍历顺序：
    • 0/1 背包内层从大到小（防止重复选取）
    • 完全背包内层从小到大（允许重复选取）
    • 多重背包：二进制拆分转化为 0/1 背包

实战案例

最长递增子序列（LeetCode 300）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

/**
 * LIS - 最长递增子序列
 * 状态定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
 * 状态转移：dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]
 * 时间复杂度：O(n²) 空间复杂度：O(n)
 */
function lengthOfLIS(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  
  const dp = new Array(n).fill(1);
  let maxLen = 1;
  
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    maxLen = Math.max(maxLen, dp[i]);
  }
  
  return maxLen;
}

/**
 * 优化版：贪心 + 二分查找
 * 维护一个数组 tails，tails[k] 表示长度为 k+1 的递增子序列的最小末尾元素
 * 时间复杂度：O(n log n)
 */
function lengthOfLISOptimized(nums) {
  const tails = [];
  
  for (const num of nums) {
    let left = 0;
    let right = tails.length;
    
    while (left < right) {
      const mid = left + ((right - left) >> 1);
      if (tails[mid] < num) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    
    tails[left] = num;
  }
  
  return tails.length;
}

底层原理

DP 的本质是 DAG 上的最短/最长路径

每一个 DP 问题都可以映射到一个有向无环图（DAG）上。状态是图的节点，状态转移是图的边，DP 的过程就是在 DAG 上按拓扑序递推。

例如爬楼梯问题：

  • 节点：0, 1, 2, …, n（每层台阶）
  • 边：从 i 到 i+1（爬1步），从 i 到 i+2（爬2步）
  • 问题：从节点 0 到节点 n 有多少条不同路径？

这个视角的意义在于：当你的 DP 状态转移不是线性时（像树形 DP、区间 DP），理解 DAG 结构能帮你正确设计遍历顺序。

最优子结构的形式化证明

如果一个问题具有最优子结构，那么原问题的最优解必然包含子问题的最优解。以背包问题为例：

假设 dp[i][j] 是前 i 件物品、容量为 j 的最优解，且这个最优解包含了第 i 件物品。那么去掉第 i 件物品后，剩下的 dp[i-1][j-w[i]] 必须是前 i-1 件物品、容量为 j-w[i] 的最优解。

证明（反证法）：如果 dp[i-1][j-w[i]] 不是最优的，存在更大的 dp'[i-1][j-w[i]]，那么 dp'[i-1][j-w[i]] + v[i] > dp[i][j]，与 dp[i][j] 是最优解矛盾。

状态压缩的数学本质

一维空间压缩实质上是将 DP 表的计算从「全量存储」改为「滑动窗口」。$dp[i][j]$ 只依赖于 $dp[i-1][*]$ 时，我们只需要保留上一行的数据。在 0/1 背包中因为每个物品只能选一次，所以采用逆序遍历来保证 $dp[j-w]$ 读取的是上一轮的值。

高频面试题解析

面试题1：打家劫舍（LeetCode 198）

问题：一排房屋，相邻不能同时偷，求能偷到的最大金额。

思路：这是一维 DP。$dp[i] = \max(dp[i-1], dp[i-2] + nums[i])$，代表两间房屋，要么偷当前这间（加上 i-2 的结果），要么不偷（继承 i-1 的结果）。

面试题2：零钱兑换（LeetCode 322）

问题：给定不同面额的硬币 coins 和一个总金额 amount，求凑成 amount 所需的最少硬币数。

思路：完全背包的变体。$dp[i] = \min(dp[i], dp[i-coin] + 1)$，其中 $dp[i]$ 表示凑 i 元所需最少硬币数。

面试题3：编辑距离（LeetCode 72）

问题：将 word1 变成 word2 的最少操作步数（增、删、替换）。

思路：二维 DP 的代表。$dp[i][j]$ 表示 word1 前 i 个字符变成 word2 前 j 个字符的最小操作数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function minDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  
  for (let i = 1; i <= m; i++) dp[i][0] = i;
  for (let j = 1; j <= n; j++) dp[0][j] = j;
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1,     // 删除
          dp[i][j - 1] + 1,     // 插入
          dp[i - 1][j - 1] + 1  // 替换
        );
      }
    }
  }
  
  return dp[m][n];
}

面试题4：最大子数组和（LeetCode 53）

问题：找出数组中连续子数组的最大和。

思路：$dp[i] = \max(nums[i], dp[i-1] + nums[i])$，要么重新开始，要么延续之前的子数组。由于 $dp[i]$ 只依赖 $dp[i-1]$，可以直接用一个变量滚动更新。

面试题5：不同的二叉搜索树（LeetCode 96）

问题：给定 n 个节点，求能组成多少种不同结构的二叉搜索树。

思路：$dp[i] = \sum_{k=1}^{i} dp[k-1] \cdot dp[i-k]$。以每个节点为根，左子树有 dp[k-1] 种，右子树有 dp[i-k] 种，乘积求和。这是卡特兰数的应用。

总结与扩展

DP 解题五步法

  1. 定义状态：dp[i][j] 代表啥？
  2. 推导转移方程：当前结果如何从之前结果得到？
  3. 确定遍历顺序：自底向上、自左向右？
  4. 初始化边界：最小的子问题的解是什么？
  5. 返回目标：最终答案在 dp 的哪个位置？

扩展方向

  • 树形 DP：在树上做 DP（如树的直径、树的最大独立集）
  • 区间 DP：状态为 dp[i][j] 表示区间 [i, j] 上的最优解（如回文子串、矩阵链乘）
  • 数位 DP：在数字的数位上进行 DP（如统计不含 4 的数字个数）
  • 状态压缩 DP：用二进制位表示状态子集（如旅行商问题 TSP）
  • 记忆化搜索：DFS + 缓存，某些复杂状态转移用递归写更自然

动态规划的学习曲线确实陡峭，但一旦掌握了思维框架，你会发现绝大多数 DP 问题都遵循着相同的基本模式。关键在于多做练习，把「状态定义→转移方程→边界条件」这一思维流程变成肌肉记忆。

数据结构与算法, 算法
动态规划 斐波那契 爬楼梯 背包问题
本文由作者按照 CC BY 4.0 进行授权

© 独行的风. 保留部分权利。

本站采用 Jekyll 主题 Chirpy

本站总访问量 次 本站访客数 人 本文阅读量 次