动态规划基础 - 学习笔记-数据结构与算法-上海佼艾

一、什么是动态规划

动态规划（Dynamic Programming，简称 DP）是算法设计中的一种核心思想，它将一个复杂问题分解为若干子问题，通过求解子问题并记录其结果，避免重复计算，从而高效地解决原问题。动态规划适用于具有最优子结构和重叠子问题性质的问题。

DP 的核心三要素：

最优子结构（Optimal Substructure）： 一个问题的最优解包含其子问题的最优解
重叠子问题（Overlapping Subproblems）： 不同的子问题会重复出现，而非每次都是新问题
无后效性（No Aftereffect）： 子问题的解一旦确定，就不受后续决策的影响

与很多人直觉相反，动态规划并非某种具体的算法，而是一种求解问题的思想框架。它的核心在于"记忆化"——不重复计算已经算过的东西。下面我们通过三个核心概念的详细讲解来深入理解动态规划的本质。

1.1 最优子结构

最优子结构意味着问题的最优解可以通过其子问题的最优解组合得到。以最短路径问题为例：如果从 A 到 C 的最短路径经过 B，那么从 A 到 B 的这段路径一定是从 A 到 B 的最短路径。这个性质使得我们能够"递推"地构建答案——先求解小问题，再组合成大问题的解。

不具备最优子结构的问题不适用 DP。例如，在一个图中找一条经过最多节点的简单路径（最长简单路径问题）就不具备最优子结构，因为子路径的最优解并不能保证组合后仍然是最优的。

1.2 重叠子问题

重叠子问题意味着在递归求解过程中，相同的子问题会被多次遇到。以斐波那契数列为例，计算 fib(5) 需要 fib(4) 和 fib(3)，而计算 fib(4) 又需要 fib(3) 和 fib(2)——fib(3) 被重复计算了两次。如果问题规模变大，重复计算的次数会呈爆炸式增长。

是否重叠是 DP 与分治法的关键区别之一。分治法（如归并排序）将问题划分为互不相交的子问题，每个子问题只出现一次；而 DP 处理的是子问题会重复出现的情况。

1.3 无后效性

无后效性（也称马尔可夫性）指某个阶段的状态一旦确定，之后的过程就只与这个状态有关，而与到达这个状态的方式无关。换句话说，"过去只影响未来通过当前状态，而不直接影响未来决策"。例如在背包问题中，我们只需要知道当前剩余容量和已考虑的物品索引，而不需要知道具体选择了哪些物品——因为后续决策只依赖于"剩余空间"这个状态量。

二、DP 的五步设计法

解决动态规划问题有一套标准的思维流程。很多初学者觉得 DP 难，是因为缺乏结构化的思考步骤。下面这个五步设计法能帮助你系统性地攻克任何 DP 问题。

步骤一：定义状态（Design State）

明确 dp[i]（或 dp[i][j]）代表什么含义。这是最关键的一步，一个好的状态定义能让问题豁然开朗。通常状态与问题的输入参数相关，如一维 DP 的索引位置、二维 DP 的坐标位置等。

步骤二：推导状态转移方程（State Transition Equation）

找到状态之间的关系，即 dp[i] 如何从之前的状态计算得来。这是 DP 的核心公式。通常需要思考：当前状态可以从哪些前置状态转移过来？转移代价是多少？

步骤三：确定初始化和边界条件（Initialize）

最小的子问题（base case）的值是什么？例如 dp[0]、dp[1] 的值。边界条件决定了递推的起点。

步骤四：确定遍历顺序（Traversal Order）

决定从前往后、从后往前、还是其他遍历方式。遍历顺序需要保证在计算当前状态时，它所依赖的状态已经被计算出来。

步骤五：返回最终结果（Return Result）

确定最终答案存储在哪个状态中。通常是 dp[n] 或 dp[m][n]，但也可能是 dp 数组中的最大值或最小值。

五步法口诀：

定义状态 → 转移方程 → 初始边界 → 遍历顺序 → 返回结果

这个框架适用于所有 DP 问题。每做一道 DP 题，都按这五步来思考，久而久之就会形成条件反射。

三、DP 的两种实现方式

3.1 自顶向下（记忆化递归）

从原问题出发，递归地求解子问题，并使用一个缓存（通常是数组或哈希表）来存储已经计算过的子问题结果。这种方式的优点是代码直观、只计算必要的子问题。缺点是有递归开销，且对于某些问题（如状态空间极大时）可能导致栈溢出。

// 记忆化递归示例：斐波那契数列
function fib(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n] !== undefined) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

// 时间复杂度：O(n)，空间复杂度：O(n)
console.log(fib(10)); // 输出 55

记忆化递归的优点是它自然地遵循了问题的递归分解结构，你只需要关注如何将大问题拆解为小问题，再加一层缓存即可。缺点是需要额外的递归栈空间，而且对于某些状态空间极大的问题可能不适用。

3.2 自底向上（表格迭代）

从最小的子问题开始，迭代地计算所有子问题的解，逐步向上构建最终答案。通常使用数组或矩阵来存储中间状态。这种方式的优点是没有递归开销、性能通常更好，且容易进一步做空间优化（如滚动数组）。

// 自底向上表格法：斐波那契数列
function fib(n) {
    if (n <= 1) return n;
    const dp = new Array(n + 1).fill(0);
    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(n)
console.log(fib(10)); // 输出 55

3.3 两种方式的对比

对比维度	自顶向下（记忆化递归）	自底向上（表格迭代）
实现方式	递归 + 缓存	迭代 + 表格
计算策略	按需计算，只计算必要的子问题	计算所有子问题
代码可读性	更直观，贴近问题定义	略抽象，但更高效
性能	有递归调用开销	无额外开销，通常更快
空间优化	难以使用滚动数组	容易做空间优化
适用场景	状态空间大但实际访问少	状态空间确定且相对较小

在实际刷题和面试中，自底向上的表格法更受推崇，因为它的性能更好且易于优化。但在理解问题阶段，先用记忆化递归理清思路也是个很好的策略。

四、经典入门例题详解

理论讲得再多，不如亲手做几道题来得实在。下面我们从最基础的题目开始，逐步递进，每道题都严格按照五步设计法来分析。

4.1 斐波那契数列（LeetCode 509）

这是 DP 的"Hello World"，虽然简单但包含了 DP 的全部要素。

// 五步法分析斐波那契数列
// 步骤1：定义状态 dp[i] 表示第 i 个斐波那契数
// 步骤2：转移方程 dp[i] = dp[i-1] + dp[i-2]
// 步骤3：初始化 dp[0] = 0, dp[1] = 1
// 步骤4：遍历顺序 从 2 到 n (正序遍历)
// 步骤5：返回结果 dp[n]

function fib(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 cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

// 空间优化：O(1)，只保留两个变量

这里我们使用滚动数组思想，将空间复杂度从 O(n) 优化到了 O(1)。因为当前状态只依赖于前两个状态，所以不需要保留整个 dp 数组。

4.2 爬楼梯（LeetCode 70）

你正在爬楼梯，每次可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到第 n 级台阶？

// 五步法分析爬楼梯
// 步骤1：定义状态 dp[i] 表示爬到第 i 级台阶的方法数
// 步骤2：转移方程 dp[i] = dp[i-1] + dp[i-2]
//          (最后一步可以是爬1阶或2阶)
// 步骤3：初始化 dp[1] = 1, dp[2] = 2
// 步骤4：遍历顺序 从 3 到 n (正序遍历)
// 步骤5：返回结果 dp[n]

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 cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

// 时间复杂度：O(n)，空间复杂度：O(1)
console.log(climbStairs(5)); // 输出 8

实际上，爬楼梯问题的状态转移方程和斐波那契数列完全一致，只是初始值不同。这是 DP 的一个重要特点：很多不同的问题共享同一个数学模型。一旦你掌握了基本的 DP 框架，就能举一反三。

4.3 不同路径（LeetCode 62）

一个机器人位于 m x n 网格的左上角，每次只能向右或向下移动一步，要到达右下角，有多少条不同的路径？

// 五步法分析不同路径
// 步骤1：定义状态 dp[i][j] 表示到达位置 (i,j) 的路径数
// 步骤2：转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]
//          (只能从上方或左方过来)
// 步骤3：初始化 dp[0][j] = 1, dp[i][0] = 1 (边界只有一种走法)
// 步骤4：遍历顺序 逐行正序遍历
// 步骤5：返回结果 dp[m-1][n-1]

function uniquePaths(m, n) {
    // 使用一维数组进行空间优化（滚动数组）
    const dp = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j - 1];
            // dp[j] 是上一行的值（上方），dp[j-1] 是当前行的左值
        }
    }
    return dp[n - 1];
}

// 时间复杂度：O(m*n)，空间复杂度：O(n)
console.log(uniquePaths(3, 7)); // 输出 28

这道题是从一维 DP 到二维 DP 的过渡。值得注意的是，我们通过滚动数组将二维 dp 压缩成了一维，每次刷新同一行数据——dp[j] 在更新前存储的是上一行同列的值（即"从上方来"），dp[j-1] 已经更新为当前行的左列值（即"从左方来"）。

4.4 最小路径和（LeetCode 64）

给定一个包含非负整数的 m x n 网格，找到一条从左上到右下的路径，使得路径上的数字总和最小。

// 五步法分析最小路径和
// 步骤1：定义状态 dp[i][j] 表示到 (i,j) 的最小路径和
// 步骤2：转移方程 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
// 步骤3：初始化 dp[0][0] = grid[0][0]，边界累积求和
// 步骤4：遍历顺序 逐行正序遍历
// 步骤5：返回结果 dp[m-1][n-1]

function minPathSum(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const dp = new Array(n).fill(0);

    // 初始化第一行（只能从左往右走）
    dp[0] = grid[0][0];
    for (let j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }

    for (let i = 1; i < m; i++) {
        // 每行第一个元素：只能从上方来
        dp[0] = dp[0] + grid[i][0];
        for (let j = 1; j < n; j++) {
            dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
        }
    }
    return dp[n - 1];
}

// 时间复杂度：O(m*n)，空间复杂度：O(n)

对比"不同路径"和"最小路径和"可以看出：两道题的状态定义和遍历方式几乎一模一样，唯一的区别在于转移方程中如何聚合前驱状态——计数问题用加法，最值问题用 min/max。这就是 DP 的模式化思维：识别模式比记忆代码更重要。

4.5 打家劫舍（LeetCode 198）

你是一个专业小偷，沿街的房屋每间都藏有现金。相邻的房屋在同一晚会触发警报。在不触发警报的前提下，你能偷到的最大金额是多少？

// 五步法分析打家劫舍
// 步骤1：定义状态 dp[i] 表示偷到第 i 间房屋时的最大金额
// 步骤2：转移方程 dp[i] = max(dp[i-1], dp[i-2] + nums[i])
//          不偷当前：dp[i-1]；偷当前：dp[i-2] + nums[i]
// 步骤3：初始化 dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
// 步骤4：遍历顺序 从 2 到 n-1 (正序遍历)
// 步骤5：返回结果 dp[n-1]

function rob(nums) {
    const n = nums.length;
    if (n === 0) return 0;
    if (n === 1) return nums[0];

    let prev2 = nums[0];                    // dp[i-2]
    let prev1 = Math.max(nums[0], nums[1]); // dp[i-1]

    for (let i = 2; i < n; i++) {
        const cur = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

// 时间复杂度：O(n)，空间复杂度：O(1)
console.log(rob([2, 7, 9, 3, 1])); // 输出 12 (偷 2+9+1)

打家劫舍引入了 DP 中的一个重要概念——决策与约束。你不能同时选择相邻的两个元素，这引入了约束条件。在状态转移中，这种约束体现在转移方程的两个分支上（偷 vs 不偷），这是 DP 处理约束优化问题的标准手法。

入门总结：五个例题的递进关系

斐波那契 → 爬楼梯 → 不同路径 → 最小路径和 → 打家劫舍

这条学习路径包含了 DP 的关键知识点：一维 DP 基础、二维 DP 入门、空间优化（滚动数组）、最值问题与计数问题的差异、约束条件下的决策优化。建议读者按这个顺序逐一掌握。

五、DP 与分治、贪心的对比

很多初学者容易混淆动态规划、分治法和贪心算法。它们都涉及"将问题分解为子问题"，但核心理念有本质区别。

对比维度	动态规划（DP）	分治法（Divide & Conquer）	贪心算法（Greedy）
子问题关系	重叠（repeating）	不相交（disjoint）	单路径（single path）
决策方式	多阶段决策，考虑所有可能	递归分解	只做当前最优选择
是否回溯	隐式回溯（状态转移）	不回溯	不回溯
典型例子	背包问题、最短路径	归并排序、快速排序	哈夫曼编码、Dijkstra
正确性保证	最优子结构（全面枚举）	数学归纳法	贪心选择性质（需严格证明）
时间复杂度	多项式级别（状态数 × 转移）	通常 O(n log n)	通常 O(n) 或 O(n log n)

核心区别一句话总结：

分治： 子问题不重叠，分解后各自独立求解再合并——如归并排序
贪心： 每一步只做局部最优选择，期望达到全局最优——需要严格证明
DP： 子问题重叠，通过记忆化避免重复计算，全面枚举状态空间

一个很好的记忆方式是：分治是树形分解（各分支独立），贪心是单线前进（不回头），DP 是图状遍历（状态间相互依赖）。

5.1 一个直观的例子

想象你要从北京到上海，中间经过若干城市：

贪心： 每一段都选当前最短的路，但可能最终不是整体最短——因为局部最优不保证全局最优
DP： 记录到达每个城市的最短距离，逐步更新——保证全局最优
分治： 不太适用，因为路径问题的子问题（A到B的最短路径和B到C的最短路径）不是独立的

这个例子的关键在于：贪心牺牲了全局最优换取速度，DP 用空间换时间保证最优，分治依赖问题本身的可分解性。

六、空间复杂度优化专题

DP 常常因为存储整个状态表格而导致较高的空间复杂度。下面介绍两种最常用的优化技巧。

6.1 滚动数组（Rolling Array）

当状态转移方程只依赖前 k 个状态时，可以用一个长度为 k 的数组滚动更新，而不是存储全部状态。前面每个例题中我们都已经使用了这一技巧。

// 原始版本：空间 O(n)
function fibO1(n) {
    const dp = new Array(n + 1).fill(0);
    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(1)
function fibO2(n) {
    if (n <= 1) return n;
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        [a, b] = [b, a + b];  // 同时更新两个变量
    }
    return b;
}

// 二维滚动数组：不同路径的空间优化
function uniquePathsOpt(m, n) {
    const dp = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}
// 二维 → 一维，空间复杂度从 O(m*n) 降至 O(n)

6.2 状态压缩（Bitmask DP）

当 DP 状态涉及集合或子集时，可以用二进制位来表示集合中元素的选择情况。这种技巧常用于旅行商问题（TSP）、任务分配等"状态压缩 DP"问题中。

// 状态压缩示例：子集求和问题
// 给定数组 nums，问是否能选出若干元素使其和为 target
function canSum(nums, target) {
    const n = nums.length;
    const dp = new Array(1 << n).fill(false);
    dp[0] = true;  // 空集可以凑出和 0

    for (let mask = 0; mask < (1 << n); mask++) {
        if (!dp[mask]) continue;
        let sum = 0;
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) sum += nums[i];
        }
        if (sum === target) return true;
        // 尝试添加新元素
        for (let i = 0; i < n; i++) {
            if (!(mask & (1 << i))) {
                dp[mask | (1 << i)] = true;
            }
        }
    }
    return false;
}

// 状态压缩的核心：用整数的二进制位表示集合状态
// 例如 mask = 0b101 表示选择了第 0 个和第 2 个元素

优化总结：

滚动数组： 适用于依赖关系局部（只依赖前 k 个状态）的场景，几乎适用于所有一维/二维 DP
状态压缩： 适用于状态为集合、元素数不超过 20-30 的场景，将指数级状态压缩到整数中
四边形不等式优化： 适用于某些区间 DP 问题，可将 O(n³) 降为 O(n²)
斜率优化（凸包优化）： 适用于转移方程形如 dp[i] = min(dp[j] + f(j) * g(i)) 的场景

七、常见 DP 问题分类

了解 DP 的常见模式，可以帮助你快速识别问题的本质。以下是几类最常见的 DP 问题：

1. 线性 DP

状态沿着一条直线递推，状态之间呈线性关系。典型问题：最大子数组和（LeetCode 53）、最长递增子序列（LeetCode 300）、乘积最大子数组（LeetCode 152）。这类问题是 DP 的基石，通常状态定义为一维数组 dp[i]，表示以第 i 个元素结尾的某种最优值。

2. 区间 DP

状态定义为区间 dp[i][j]，表示从 i 到 j 这个区间内的最优解。典型问题：最长回文子串（LeetCode 5）、戳气球（LeetCode 312）、合并石子（经典题）。这类问题的转移通常需要枚举区间内的分割点。

3. 背包 DP

在限定的容量下选择物品，使总价值最大。包括 0-1 背包、完全背包、多重背包等。典型问题：分割等和子集（LeetCode 416）、零钱兑换（LeetCode 322）、目标和（LeetCode 494）。背包问题是面试中的绝对高频考点。

4. 树形 DP

在树结构上做动态规划，通常结合 DFS 遍历。典型问题：二叉树中的最大路径和（LeetCode 124）、打家劫舍 III（LeetCode 337）、树的直径。树形 DP 的核心在于递归处理子树，然后将子树结果向上合并。

5. 数位 DP

在数字的十进制/二进制表示上进行 DP，解决"范围内满足条件的数字个数"这类问题。典型问题：数字 1 的个数（LeetCode 233）、不含连续 1 的非负整数（LeetCode 600）。

6. 状压 DP

使用二进制位表示集合状态，在前面"状态压缩"部分已详细介绍。典型问题：旅行商问题、愤怒的小鸟（LeetCode 312 变体）。

八、DP 解题的常见错误与调试技巧

8.1 常见错误

状态定义不当： 状态定义过于复杂或过于简单，导致无法写出正确的转移方程。建议从最简单直观的定义开始尝试。
遗漏状态维度： 当问题涉及多个约束条件时，状态维度不够。例如背包问题漏掉了"容量"这个维度。
转移方程遗漏分支： 有些状态可能有多个来源，遗漏一个分支就会出错。建议用状态转移图来辅助思考。
初始化错误： base case 的值不对，或者数组越界。建议在纸上模拟小规模数据验证。
遍历顺序错误： 计算 dp[i] 时它依赖的状态还没算完。建议检查循环的方向是否正确。

8.2 调试技巧

调试 DP 的四个技巧

打印 dp 表： 在循环中加入 console.table(dp) 或类似的打印语句，观察每个状态的更新过程
小规模验证： 先用 n=1,2,3 的简单输入手动模拟，然后与程序输出对比
边界测试： 检查 n=0, n=1, 空数组等极端情况是否处理正确
对拍验证： 先用暴力递归（不优化）写一个正确版本，再与 DP 版本进行对拍验证

// 调试技巧示例：打印打家劫舍的 DP 表
function robDebug(nums) {
    const n = nums.length;
    if (n === 0) return 0;
    const dp = new Array(n).fill(0);
    dp[0] = nums[0];
    if (n > 1) dp[1] = Math.max(nums[0], nums[1]);

    for (let i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        console.log(`dp[${i}] = max(dp[${i-1}]=${dp[i-1]}, dp[${i-2}]=${dp[i-2]} + nums[${i}]=${nums[i]}) = ${dp[i]}`);
    }
    console.table(dp);
    return dp[n - 1];
}

robDebug([2, 7, 9, 3, 1]);
// 输出如下：
// dp[2] = max(dp[1]=7, dp[0]=2 + nums[2]=9) = 11
// dp[3] = max(dp[2]=11, dp[1]=7 + nums[3]=3) = 11
// dp[4] = max(dp[3]=11, dp[2]=11 + nums[4]=1) = 12

十、进一步思考与练习

掌握了动态规划的基础知识后，下面是几个进阶方向供你继续探索：

学习建议：

每道题都严格按五步法分析，即使是很简单的问题
同时尝试记忆化递归和表格迭代两种写法
做完后尝试空间优化，看能否将空间降一个量级
用暴力法验证 DP 解法的正确性
建立错题本，记录每道题的状态定义和转移方程

"动态规划不是背模板，而是培养一种思维方式。当你看到一个问题能自然地想到'这个状态的解可以由哪些更小的状态转移而来'时，你就真正掌握了 DP。"