【数据结构与算法体系】之动态规划

一、动态规划的核心思想

动态规划（Dynamic Programming，DP）是一种通过将复杂问题分解为子问题，并存储子问题的解以避免重复计算来求解最优化问题的算法设计技巧。DP这个名称本身有一定误导性——它并非特指某种“动态”的过程，而是Richard Bellman在20世纪50年代命名时，为了在当时的研究环境中使这种数学方法听起来更“合理”而选择的词汇。

一个问题能用DP求解，必须满足两个关键性质。最优子结构（Optimal Substructure）：问题的最优解包含其子问题的最优解。也就是说，我们可以通过组合子问题的最优解来构造全局最优解。重叠子问题（Overlapping Subproblems）：在递归求解过程中，相同的子问题被重复计算多次。DP通过将子问题的解存储在表格中，将重复计算转化为查表操作，实现了用空间换时间。

与分治法的区别：分治法也将问题分解为子问题，但子问题是互不重叠的（如归并排序的左右两部分独立），因此不需要存储子问题的解。与贪心算法的区别：贪心算法在每个步骤做出当时看起来最优的选择，但不能保证全局最优（除非问题具有贪心选择性质）；DP系统地考虑了所有可能的决策组合。

二、DP的两种实现方式

自顶向下（Top-Down）——记忆化搜索（Memoization）：从原始问题出发，递归地求解子问题。每当计算出一个子问题的解，就将其存储在记忆化数组（或哈希表）中。下次遇到相同的子问题时，直接从数组中取出结果，不再递归计算。本质上是对暴力递归的缓存优化。

自底向上（Bottom-Up）——表格法（Tabulation）：从最小的子问题开始，逐步填充DP表格，直到求出原始问题的解。通常使用迭代而非递归，避免了递归调用的开销和栈溢出风险。

以斐波那契数列为例对比两种方式。自顶向下：

int[] memo = new int[n + 1];
Arrays.fill(memo, -1);

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

自底向上：

int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
// 空间优化：只保留前两个值
int fibOptimized(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

自顶向下只在需要时计算子问题（可能跳过某些不需要的子问题），但递归调用有额外开销。自底向上计算所有子问题（即使某些子问题的结果最终未被使用），但迭代效率高且可以优化空间复杂度。对于大多数DP问题，面试中通常实现自底向上版本，因为可以直接看出时间和空间复杂度，并且容易进一步空间优化（如滚动数组）。

三、0/1 背包问题

0/1 背包问题是最经典的DP问题之一：给定N个物品，每个物品有重量w[i]和价值v[i]，和一个容量为W的背包。每个物品要么完整放入（选择1），要么不放入（选择0），不能部分放入。求在总重量不超过背包容量的条件下，能获得的最大总价值。

状态定义：dp[i][j] 表示考虑前 i 个物品，背包容量为 j 时能获得的最大价值。

状态转移方程：

dp[i][j] = max(dp[i-1][j],                    // 不选第i个物品
               dp[i-1][j-w[i]] + v[i])         // 选第i个物品（如果 j >= w[i]）

边界条件：dp[0][j] = 0（没有物品时价值为0），dp[i][0] = 0（容量为0时价值为0）。

int knapsack(int W, int[] w, int[] v, int N) {
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i - 1][j]; // 不选
            if (j >= w[i - 1]) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
            }
        }
    }
    return dp[N][W];
}

空间优化：观察状态转移方程，dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-w[i]]，即只依赖上一行的数据。我们可以使用一维数组，但需要从右往左遍历容量（避免本轮的更新覆盖掉还需要使用的上一轮数据）：

int knapsackOptimized(int W, int[] w, int[] v, int N) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < N; i++) {
        for (int j = W; j >= w[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

时间复杂度和空间复杂度分别为O(N × W)和O(W)。注意0/1 背包是伪多项式算法——如果W很大（如10^9），算法不可行。这正是NP-hard问题（0/1 背包是NP-hard）的典型特征：输入数字W的编码长度是log W，而算法运行时间依赖于W本身的值（指数于输入长度）。

完全背包问题：每个物品可以选择无限次。只需将内循环方向改为从左往右（表示同一物品可以多次选择）：

for (int i = 0; i < N; i++) {
    for (int j = w[i]; j <= W; j++) {  // 注意：从左往右
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

四、最长公共子序列（LCS）

求两个字符串的最长公共子序列（可不连续）。例如，”abcde”和”ace”的LCS是”ace”，长度为3。

状态定义：dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度。

状态转移方程：

如果 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])  // 跳过不匹配的字符

int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(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];
}

如果要求输出具体的LCS序列（而不只是长度），可以从dp[m][n]回溯：如果text1[i-1] == text2[j-1]，该字符属于LCS，记录后向左上方移动；否则根据dp[i-1][j]和dp[i][j-1]的大小决定移动方向。这也称为“打印DP路径”。

五、编辑距离（Edit Distance / Levenshtein Distance）

将字符串word1转换为word2所需的最少操作次数，允许的操作有：插入一个字符、删除一个字符、替换一个字符。例如，”horse”到”ros”的编辑距离为3（horse → rorse 替换h为r，rorse → rose 删除r，rose → ros 删除e）。

状态定义：dp[i][j] 表示 word1[0..i-1] 转换为 word2[0..j-1] 的最少操作数。

状态转移方程：

如果 word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]      // 字符相同，无需操作
否则:
    dp[i][j] = 1 + min(
        dp[i-1][j],    // 删除 word1[i-1]
        dp[i][j-1],    // 在 word1 中插入 word2[j-1]
        dp[i-1][j-1]   // 替换 word1[i-1] 为 word2[j-1]
    )

int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i; // 全部删除
    for (int j = 0; j <= n; j++) dp[0][j] = j; // 全部插入
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j],
                           Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
            }
        }
    }
    return dp[m][n];
}

编辑距离在模糊搜索、拼写检查、DNA序列比对等领域有广泛应用。Linux的diff命令背后就是基于编辑距离的算法（Myers差分算法是其一种线性空间优化）。

六、硬币找零问题

给定不同面值的硬币coins[]和一个总金额amount，求组成该金额所需的最少硬币数。每种硬币数量无限（完全背包的特例）。例如coins = [1, 2, 5], amount = 11，最少需要3枚（5+5+1）。

状态定义：dp[i] 表示组成金额 i 所需的最少硬币数。

状态转移方程：

dp[i] = min(dp[i - coin] + 1)  对所有 coin ∈ coins 且 coin ≤ i

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // 初始化为不可能的大值
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

注意初始化为amount + 1而非Integer.MAX_VALUE，因为后者加1会溢出为负数。时间复杂度O(amount × N)，N为硬币种数。

七、DP解题方法论总结

解决DP问题的通用步骤：第一，识别DP信号——求最值（最大/最小/最长/最短）、求方案数（多少种方式）、问题可以分解为重复的子问题。第二，定义状态——明确dp[i]或dp[i][j]代表什么含义。好的状态定义让转移方程自然涌现。第三，推导状态转移方程——思考当前状态可以从哪些前驱状态转移而来，需要做什么选择（取或不取、选哪个）。第四，确定边界条件——最小的子问题的解是什么（通常dp[0]或dp[0][0]等）。第五，确定遍历顺序——保证计算某个状态时，它依赖的前驱状态已经被计算过了。第六，考虑空间优化——能否用滚动数组或一维数组代替二维数组。

常见的DP类型包括：线性DP（爬楼梯、打家劫舍、最大子数组和）、区间DP（矩阵链乘法、戳气球）、背包DP（0/1 背包、完全背包、多重背包）、状态压缩DP（TSP旅行商问题，用二进制位表示集合）、树形DP（树上的最大独立集）、计数DP（不同路径、解码方法）。

八、面试常见追问

问题一：DP中自顶向下和自底向上如何选择？

自顶向下（记忆化搜索）的优点是只计算所需的子问题，在处理稀疏的子问题空间时效率更高；代码实现也更接近问题的自然递归结构，容易编写和调试。缺点是递归调用有栈溢出风险（数据规模大时）和函数调用开销。自底向上（迭代）的优点是效率高（无递归开销）、可以精确控制空间复杂度（滚动数组优化）；缺点是需要仔细设计遍历顺序，可能需要计算一些不会被用到的子问题。面试中通常偏好自底向上，因为它直接展示了完整的时间/空间复杂度。

问题二：什么是“无后效性”？

无后效性（No Aftereffect）是DP适用性的关键条件之一：某个状态一旦确定，其后续的决策不受之前如何到达该状态的影响。也就是说，我们只关心“当前状态是什么”，而不关心“是怎样到达当前状态的”。例如，在背包问题中，dp[5][10]（前5个物品，容量10时的最大价值）只依赖于这个值本身，后续物品的选择不需要知道前5个物品具体选了哪些。如果问题不满足无后效性（如带有时间顺序的调度问题），可能需要增加状态维度来“记住”更多信息，使其转化为满足无后效性的形式。

问题三：背包问题的各种变体如何区分？

0/1背包：每个物品只能选一次，内循环从右往左。完全背包：每个物品可选无限次，内循环从左往右。多重背包：每个物品有数量限制，可以转化为0/1背包（二进制拆分优化：将k个物品拆分为1,2,4,…,2^m,k-2^(m+1)+1组，每组视为一个新物品，总物品数从k降至log k）。恰好装满：初始化dp[0]=0，其余为负无穷（表示不可能状态），转移方程不变。求方案数：将max改为sum，初始化dp[0]=1。输出具体选择方案：等价于打印DP回溯路径。