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

一、动态规划的核心思想

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

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

更深层的理论框架：DP本质上是对状态空间的有向无环图（DAG）的最短/最长路径求解。每个状态对应DAG中的一个节点，状态转移对应有向边，边界条件对应源节点。DP的求解顺序就是DAG的拓扑排序。这个视角统一了所有DP问题——只要我们能将问题建模为DAG上的路径问题，就能使用DP。

与分治法的区别：分治法也将问题分解为子问题，但子问题是互不重叠的（如归并排序的左右两部分独立），因此不需要存储子问题的解。与贪心算法的区别：贪心算法在每个步骤做出当时看起来最优的选择，但不能保证全局最优（除非问题具有贪心选择性质）；DP系统地考虑了所有可能的决策组合。与回溯法的区别：回溯法（DFS + 剪枝）暴力搜索整个解空间，DP通过存储子问题结果避免了指数级别的重复探索。

无后效性（No Aftereffect）是DP适用性的第三个关键条件，经常被忽略但同样重要：某个状态一旦确定，其后续的决策不受之前如何到达该状态的影响。形式化地说，给定当前状态，未来状态的条件概率分布与过去状态独立——这是一个典型的马尔可夫性质。如果问题不满足无后效性（如带有复杂时序依赖的调度问题），我们需要增加状态维度来”记住”更多历史信息，使其转化为满足无后效性的形式。

二、DP的两种实现方式与复杂度分析

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

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

两者的计算复杂度关系：如果总共有S个不同的子问题，每个子问题平均依赖d个其他子问题，则两种方法的时间复杂度均为O(S × d)。空间复杂度方面，自顶向下需要O(S)的存储空间加上O(递归深度)的调用栈空间；自底向上的空间复杂度取决于我们需要保留多少历史状态（通常可以滚动数组优化）。

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

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;
}

滚动数组（Rolling Array）是DP空间优化的核心技术。当状态转移方程中dp[i]仅依赖dp[i-1]（或dp[i-k]对于小的常数k）时，我们不需要保留完整的dp数组，只需保留最近k行的数据。在0/1背包中我们用它把O(NW)的空间降到O(W)；在斐波那契中把O(N)降到O(1)。更一般地，如果dp[i][j]仅依赖dp[i-1][…]，我们可以用一个二维数组只存两行，交替使用（dp[i % 2][j]），减少一半内存。

自顶向下只在需要时计算子问题（可能跳过某些不需要的子问题），但递归调用有额外开销。自底向上计算所有子问题（即使某些子问题的结果最终未被使用），但迭代效率高且可以优化空间复杂度。对于大多数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];
}

最优子结构的证明：设Y = {y1, y2, …, yN}是0/1背包实例的一个最优解（yi ∈ {0,1}表示第i个物品是否被选）。我们需要证明：{y2, y3, …, yN}是子实例（物品2..N，容量W - y1×w1）的最优解。假设不是，则存在子实例的更优解{z2, …, zN}，使得总价值更高。那么{y1, z2, …, zN}的价值将大于Y的价值，与Y是最优解矛盾。由此，最优子结构得证。

空间优化：观察状态转移方程，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];
}

关键细节：为什么从右往左？因为dp[j-w[i]]代表的是上一轮（第i-1个物品）的状态。如果从左往右遍历，dp[j-w[i]]可能已经在当前轮（第i个物品）被更新过，变成了包含第i个物品的状态。这样每个物品就可能被选择多次——这正是完全背包的逻辑。0/1背包的从右往左确保了每个物品只被考虑一次。

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

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

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]);
    }
}

为什么从左往右允许多次选择？当处理第i个物品且容量为j时，dp[j-w[i]]可能已经包含了第i个物品（因为它是在当前轮中计算并更新的），此时再选第i个物品相当于”在已选第i个物品的基础上再选一次”。

多重背包：每个物品i有c[i]个可用。处理方法——二进制拆分优化。不将c[i]个相同物品作为c[i]个独立的0/1物品（这会导致O(N × W × max(c))的复杂度），而是将c[i]拆分为若干组，每组大小为1, 2, 4, …, 2^k, c[i] - 2^(k+1) + 1。任意0到c[i]的数都可以表示为这些组的子集和。拆分后的组数从c[i]降到O(log c[i])，每组视为一个0/1背包物品处理。

恰好装满的变体：如果要求恰好装满背包（总重量严格等于W），初始化方式不同：dp[0] = 0，其余dp[j] = -∞（表示”不可能达到”状态）。转移方程不变，最终如果dp[W] == -∞则表示无法恰好装满。

求方案数：将max操作改为sum，初始化dp[0] = 1。转移：dp[j] = dp[j] + dp[j-w[i]]（0/1背包仍从右往左）。

输出具体选择方案：在二维dp数组中，从dp[N][W]开始回溯。若dp[i][j] == dp[i-1][j]，说明未选第i个物品，上移；否则说明选了第i个物品，记录该物品，然后移动到dp[i-1][j-w[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];
}

空间优化版本（O(min(m,n)) 空间）：注意到dp[i][j]只依赖当前行和上一行，我们可以使用两行滚动数组：

int LCS_optimized(String text1, String text2) {
    // 确保text2是较短的字符串以节省空间
    if (text1.length() < text2.length()) {
        return LCS_optimized(text2, text1);
    }
    int m = text1.length(), n = text2.length();
    int[] dp = new int[n + 1];
    for (int i = 1; i <= m; i++) {
        int prev = 0; // 保存 dp[i-1][j-1]
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[j] = prev + 1;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
            prev = temp;
        }
    }
    return dp[n];
}

这个一维数组优化的精妙之处在于变量prev的使用——它在内循环的每一步保存了”左上角”（dp[i-1][j-1]）的值，因为在更新dp[j]之前我们将旧值暂存下来。

回溯输出LCS字符串：

String getLCS(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    // ... 填充dp数组（同前）...
    
    StringBuilder sb = new StringBuilder();
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
            sb.append(text1.charAt(i - 1));
            i--; j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    return sb.reverse().toString();
}

最长公共子串（Longest Common Substring）：与LCS不同，要求公共子串是连续的。状态定义相同，但转移方程不同：当字符匹配时，dp[i][j] = dp[i-1][j-1] + 1；不匹配时，dp[i][j] = 0（因为要求连续，一旦不匹配就要重新开始）。最终答案是所有dp[i][j]的最大值而非dp[m][n]。时间复杂度O(mn)，空间可优化到O(min(m,n))。

最短公共超序列（Shortest Common Supersequence）：包含两个字符串作为子序列的最短字符串。长度 = m + n - LCS长度。构造方法：在回溯LCS的过程中，将非LCS字符也加入结果中。

五、编辑距离（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];
}

Damerau-Levenshtein距离是编辑距离的扩展，额外允许”交换两个相邻字符”的操作（键盘输入常见的typo）。转移方程需要额外处理：当i>1且j>1且word1[i-1]==word2[j-2]且word1[i-2]==word2[j-1]时，dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1)。

编辑距离在模糊搜索（Elasticsearch的fuzzy query）、拼写检查、DNA序列比对（Needleman-Wunsch算法）等领域有广泛应用。Linux的diff命令背后就是基于编辑距离的算法——Myers差分算法是编辑距离的一种线性空间优化，核心思想是将编辑距离的dp表对角线化，使用贪心算法在O((M+N)D)时间内求解（D为编辑距离）。

六、矩阵链乘法（Matrix Chain Multiplication）

给定一系列矩阵A1, A2, …, An（矩阵Ai的维度为p[i-1] × p[i]），求完全括号化这些矩阵相乘的方式，使得标量乘法次数最少。矩阵乘法的结合律保证了无论怎么加括号，结果相同，但计算代价可能差异巨大——例如A(10×100), B(100×5), C(5×50)：(AB)C需10×100×5 + 10×5×50 = 7500次乘法；A(BC)需100×5×50 + 10×100×50 = 75000次乘法，相差10倍。

状态定义：dp[i][j] 表示计算子链 Ai…Aj 所需的最少标量乘法次数。

状态转移方程：

dp[i][j] = min{ dp[i][k] + dp[k+1][j] + p[i-1] × p[k] × p[j] } 对所有 i ≤ k < j

边界条件：dp[i][i] = 0（单个矩阵无需乘法）。

int matrixChainOrder(int[] p) {
    int n = p.length - 1;  // 矩阵数量
    int[][] dp = new int[n][n];
    
    // len 是子链长度
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                }
            }
        }
    }
    return dp[0][n - 1];
}

这个问题的独特之处在于它属于区间DP——状态由区间[i, j]定义，遍历顺序必须按区间长度递增（因为计算长区间需要短区间的结果）。时间复杂度O(N³)，空间复杂度O(N²)。

七、股票买卖问题（通用DP框架）

LeetCode上有一系列股票买卖问题，其实都可以用统一的DP框架解决。问题的变体包括：最多交易K次、有冷冻期（cooldown）、有交易手续费等。

通用状态定义：dp[i][k][s] 表示第i天结束时，最多进行k次交易，持有状态为s（0表示不持有股票，1表示持有股票）时的最大利润。

通用状态转移方程：

dp[i][k][0] = max(dp[i-1][k][0],                // 继续不持有
                  dp[i-1][k][1] + prices[i])     // 卖出
dp[i][k][1] = max(dp[i-1][k][1],                // 继续持有
                  dp[i-1][k-1][0] - prices[i])   // 买入（买入算一次交易的开始）

边界条件：dp[0][k][0] = 0，dp[0][k][1] = -∞（第0天不可能持有股票）。最终答案为dp[n-1][K][0]（最后一天不持有股票的状态）。

各变体对应状态简化：

• 无限交易（K = ∞）：省略k维度，dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])，dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])。
• K=1（一次交易）：进一步简化，只需要记录买入后的最低点。
• 含冷冻期：买入时从dp[i-2][0]转移（因为dp[i-1][0]可能包含当天卖出、第二天不能买入的限制）。
• 含手续费：卖出时扣除手续费：dp[i-1][k][1] + prices[i] - fee。

这种统一视角展示了DP的威力——多个看似不同的问题实际上是同一框架的特殊情况。

八、正则表达式匹配

LeetCode第10题（Hard）：实现支持’.’和’‘的正则表达式匹配。’.’匹配任意单个字符，’‘匹配零个或多个前面的元素。

状态定义：dp[i][j] 表示 s[0..i-1] 是否能被 p[0..j-1] 匹配。

状态转移分析（这是DP状态转移复杂性的典型代表）：

1. 如果p[j-1]是普通字符：dp[i][j] = (s[i-1] == p[j-1]) && dp[i-1][j-1]
2. 如果p[j-1]是’.’：dp[i][j] = dp[i-1][j-1]（’.’匹配任意单字符）
3. 如果p[j-1]是’*’（最复杂的情况）：
   • 零次匹配（忽略p[j-2]和p[j-1]）：dp[i][j] = dp[i][j-2]
   • 一次或多次匹配：需要s[i-1]与p[j-2]匹配：如果s[i-1] == p[j-2]或p[j-2] == '.'，则dp[i][j] = dp[i-1][j]（因为’*’可以匹配多个，所以s回退一位但p保持不变）

boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    
    // 处理空字符串匹配模式的情况（如 "a*b*c*" 可以匹配空串）
    for (int j = 2; j <= n; j++) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char sc = s.charAt(i - 1);
            char pc = p.charAt(j - 1);
            if (pc == '*') {
                dp[i][j] = dp[i][j - 2]; // 零次匹配
                char pre = p.charAt(j - 2);
                if (pre == '.' || pre == sc) {
                    dp[i][j] |= dp[i - 1][j]; // 一次或多次匹配
                }
            } else if (pc == '.' || pc == sc) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
}

这个例子展示了DP问题中状态转移方程可能相当复杂——需要仔细分析输入字符的不同类型（普通字符、通配符、量词符），并正确表达它们之间的逻辑关系。

九、最长递增子序列（LIS）与耐心排序

问题：给定无序整数数组，求其中最长递增子序列的长度（子序列不需要连续）。

经典O(N²)解法：dp[i]表示以nums[i]结尾的LIS长度。

dp[i] = max(dp[j] + 1) 对所有 j < i 且 nums[j] < nums[i]

耐心排序（Patience Sort）O(N log N)解法：这个精巧的解法将LIS问题转化为维护”牌堆”。想象我们在处理一副牌，规则是：每张牌只能放在点数比它大的最左边的牌堆顶部。牌堆的数量就是LIS的长度。算法实现时，我们维护一个tails数组，tails[k]表示长度为k+1的递增子序列的最小结尾元素。tails数组始终递增，因此可以用二分查找定位每张牌应该放入的堆。

int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int i = 0, j = size;
        while (i < j) {  // 二分查找第一个 >= x 的位置
            int m = (i + j) / 2;
            if (tails[m] < x) i = m + 1;
            else j = m;
        }
        tails[i] = x;
        if (i == size) size++;
    }
    return size;
}

这个O(N log N)解法的正确性基于一个关键的不变性：tails数组始终是递增的。证明：假设在插入x时，它被放在位置i（即替换了tails[i]），这意味着tails[i-1] < x ≤ tails[i]（或i=0时tails[0] > x）。由于x ≤ 旧的tails[i]，tails数组仍然保持递增。又因为每次替换都是从左到右找到的第一个≥x的位置，tails的递增性得以维持。

如果想要输出具体的LIS序列（而不只是长度），需要额外维护每个元素在LIS中的前驱索引，即在tails数组中记录的是索引而非值。

十、DP解题方法论总结与常见类型

解决DP问题的通用步骤：

第一步：识别DP信号——求最值（最大/最小/最长/最短）、求方案数（多少种方式）、求可行性（是否能达到某个状态）。当问题可以分解为重复的子问题，且存在最优子结构时，DP是最可能的方法。

第二步：定义状态——这是DP最核心也是最困难的一步。一个好的状态定义满足：（1）能够唯一描述一个子问题；（2）能够通过状态转移推导出更大的子问题；（3）状态空间不要太大（避免状态爆炸）。常见的状态维度包括：序列位置（i, j）、容量/限制、持有状态、选与不选、集合（用bit mask表示）。

第三步：推导状态转移方程——思考当前状态可以从哪些前驱状态转移而来，需要做什么选择（取或不取、选哪个）。列出所有可能的决策，对每个决策写出对应的前驱状态。

第四步：确定边界条件——最小的子问题的解是什么。这通常是dp[0]、dp[0][0]或dp[i][i]等基本情况。边界条件决定了DP的自底向上的起点。

第五步：确定遍历顺序——保证计算某个状态时，它依赖的前驱状态已经被计算过了。对于序列DP通常从小到大遍历索引；对于区间DP通常按长度递增遍历；对于背包DP，0/1背包从右往左，完全背包从左往右。

第六步：考虑空间优化——能否用滚动数组或一维数组代替二维数组。检查状态转移是否只依赖有限的几个历史状态。

常见的DP类型分类：

• 线性DP：爬楼梯、打家劫舍、最大子数组和（Kadane算法）
• 背包DP：0/1背包、完全背包、多重背包、分组背包
• 区间DP：矩阵链乘法、戳气球、石子合并
• 双序列DP：LCS、编辑距离、正则表达式匹配
• 状态压缩DP：TSP旅行商问题（用二进制位表示已访问城市的集合）、集合覆盖
• 树形DP：树上的最大独立集、树的最长路径（直径）、树形背包
• 计数DP：不同路径、解码方法、整数拆分
• 概率DP：期望步数、骰子问题
• 数位DP：统计区间内满足某种性质的数字个数（如不含4的数字个数）

树形DP的典型例子——二叉树的最大独立集（选择一些节点，使得任意两个被选节点不相邻）。状态定义：dp[node][0]表示不选node时其子树的最大独立集大小；dp[node][1]表示选node时的最大独立集大小。转移：dp[node][0] = sum(max(dp[child][0], dp[child][1]))（不选node则子节点可选可不选）；dp[node][1] = 1 + sum(dp[child][0])（选了node则所有子节点都不能选）。使用后序遍历自底向上计算。

十一、面试常见追问

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

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

问题二：什么是”无后效性”，如果问题不满足怎么办？

无后效性（No Aftereffect）是DP适用性的关键条件之一：某个状态一旦确定，其后续的决策不受之前如何到达该状态的影响。形式化地说，给定当前状态，未来的决策与过去的历史条件独立。例如，在背包问题中，dp[5][10]（前5个物品，容量10时的最大价值）只依赖于这个值本身，后续物品的选择不需要知道前5个物品具体选了哪些。如果问题不满足无后效性（如带有复杂时间顺序依赖的调度问题），我们可以通过增加状态维度来记录必要的决策历史，使其转化为满足无后效性的形式。例如，在带有冷却时间的股票买卖问题中，增加一个维度记录”是否处于冷冻期”；在带有前置约束的任务选择问题中，使用状态压缩（bit mask）记录已选择的任务集合。关键思想是：将影响未来决策的所有历史信息编码进状态中。

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

0/1背包：每个物品只能选一次，内循环从右往左。完全背包：每个物品可选无限次，内循环从左往右。多重背包：每个物品有数量限制，通过二进制拆分转化为O(log c[i])个0/1背包物品。分组背包：物品分为若干组，每组内最多选一个——外层循环遍历组，中层从右往左遍历容量，内层遍历组内物品。恰好装满：初始化dp[0]=0，其余为负无穷（表示不可能状态）。求方案数：将max改为sum，初始化dp[0]=1。输出具体选择方案（字典序最小）：定义状态时考虑顺序，通常需从前向后DP再从后向前回溯。二维费用背包：增加一个维度表示第二种资源约束（如不仅有重量限制还有体积限制）。

问题四：如何证明一个DP状态转移方程的正确性？

使用数学归纳法。首先验证边界条件满足最优解的定义。然后假设对于所有依赖的状态（状态空间DAG中的前驱节点），dp值等于对应子问题的最优解。根据最优子结构，当前问题的最优解可以由某个决策加上对应子问题的最优解构成。我们枚举了所有可能的决策，并取最优值，因此dp等于当前问题的最优解。关键在于：确保枚举了所有可能的决策；确保子问题的最优解确实适用于原问题（最优子结构成立）；确保状态转移的顺序满足无后效性。

问题五：空间优化时为什么0/1背包要从右往左遍历？

因为状态转移使用了一维数组后，dp[j]既代表dp[i][j]（当前轮的目标）又会在遍历到更大的j时作为dp[i-1][j]（上一轮的数据）。如果从左往右遍历，当我们计算dp[j]时，dp[j-w[i]]可能已经被当前轮更新过了（因为它小于j，已经遍历过了），变成了dp[i][j-w[i]]而非我们需要的dp[i-1][j-w[i]]。这意味着我们允许了同一个物品被多次选择——这恰好是完全背包的需求。反过来，从右往左遍历确保dp[j-w[i]]还保留着上一轮的值（因为j-w[i] < j，在右往左遍历中还没被更新）。这个细节是背包DP中最容易出错的地方，也展示了遍历顺序对DP正确性的深刻影响。

问题六：DP中如何处理需要输出具体方案（而非仅最优值）的问题？

输出具体方案需要”回溯路径”。方法是在DP过程中额外记录choice[i]（或choice[i][j]），表示在状态(i, j)处做出了哪个决策。定义方式例如：choice[i][j] = 0表示不选第i个物品，choice[i][j] = 1表示选第i个物品。DP填表完成后，从最终状态出发（如dp[N][W]），根据choice数组一步步回溯到起点，记录沿途的决策。以0/1背包为例：

List<Integer> getSelectedItems(int[] w, int[] v, int W) {
    int N = w.length;
    int[][] dp = new int[N + 1][W + 1];
    boolean[][] choice = new boolean[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 - 1][j - w[i - 1]] + v[i - 1] > dp[i][j]) {
                dp[i][j] = dp[i - 1][j - w[i - 1]] + v[i - 1];
                choice[i][j] = true;
            }
        }
    }
    List<Integer> result = new ArrayList<>();
    int j = W;
    for (int i = N; i >= 1; i--) {
        if (choice[i][j]) {
            result.add(i - 1);
            j -= w[i - 1];
        }
    }
    Collections.reverse(result);
    return result;
}

如果要求”字典序最小”的方案，通常需要调整状态定义方向——从后往前DP，使得回溯时从前往后可以优先选择编号小的物品。

问题七：DP与记忆化搜索在复杂状态空间（非数组索引）时如何选择？

当状态空间不是简单的整数索引（如二维网格坐标）而是复杂结构（如字符串、集合、图的节点）时，记忆化搜索通常比表格法更自然。典型场景包括：博弈DP（Minimax + Alpha-Beta剪枝，状态是当前局面的哈希）；树形DP（需要后序遍历，状态是树节点引用）；状态压缩DP中状态是bit mask（虽然可以映射为整数索引，但递归结构更清晰）。选择标准：（1）如果状态空间稀疏（很多状态在求解过程中不会被访问），记忆化搜索跳过无用状态更高效；（2）如果状态维度多且遍历顺序不明显，记忆化搜索免去手动确定拓扑序的麻烦；（3）如果问题的递归结构天然清晰（如博弈树），自顶向下更直观。