动态规划算法精解：从背包问题到树形DP实战

1. 动态规划核心思想与解题框架动态规划Dynamic Programming作为算法领域的屠龙技本质上是通过将原问题分解为相互重叠的子问题并存储子问题的解来避免重复计算。这种思想在解决最优化问题时尤为有效特别是那些具有重叠子问题和最优子结构特性的场景。我接触动态规划的第一道题是经典的爬楼梯问题当时花了整整三天才真正理解状态转移方程的含义。现在回头看动态规划的核心可以归纳为三个关键步骤定义状态明确dp数组或变量的含义建立状态转移方程找出问题与子问题之间的关系式确定边界条件设置初始状态值以斐波那契数列为例其DP解法清晰地展示了这三个步骤int fib(int n) { if (n 1) return n; int dp[n1]; dp[0] 0; // 边界条件 dp[1] 1; // 边界条件 for (int i 2; i n; i) { dp[i] dp[i-1] dp[i-2]; // 状态转移 } return dp[n]; }关键提示写DP代码时建议先用注释明确标出这三个部分能大幅降低出错概率。我在面试候选人时发现能清晰划分这三个步骤的开发者DP题正确率普遍高出50%。2. 背包问题从01背包到完全背包背包问题是动态规划的必修课也是大厂面试最高频的题型之一。根据物品是否可重复选取主要分为01背包和完全背包两大类型。2.1 01背包标准解法01背包的经典描述是有N件物品和一个容量为V的背包第i件物品体积为w[i]价值为v[i]求解将哪些物品装入背包可使价值总和最大。其核心状态转移方程为dp[j] max(dp[j], dp[j-w[i]] v[i])C语言实现模板int knapsack(int W, int wt[], int val[], int n) { int dp[W1]; memset(dp, 0, sizeof(dp)); for (int i 0; i n; i) { for (int j W; j wt[i]; j--) { dp[j] fmax(dp[j], dp[j - wt[i]] val[i]); } } return dp[W]; }易错点内层循环必须倒序遍历否则会变成完全背包。这是我初学时踩过的坑导致在LeetCode上连错3次提交。2.2 完全背包变种完全背包与01背包的区别在于物品可以无限次选取只需将内层循环改为正序即可for (int j wt[i]; j W; j) { dp[j] fmax(dp[j], dp[j - wt[i]] val[i]); }实际应用中背包问题有诸多变体恰好装满问题初始化为-INF组合数问题如零钱兑换多维费用背包增加状态维度3. 最长公共子序列与字符串DP字符串相关的动态规划问题往往需要二维DP数组来表示状态其中最长公共子序列(LCS)是最典型的代表。3.1 LCS标准解法给定两个字符串text1和text2返回它们的最长公共子序列长度。状态定义dp[i][j] 表示text1[0..i-1]和text2[0..j-1]的LCS长度状态转移方程if (text1[i-1] text2[j-1]) dp[i][j] dp[i-1][j-1] 1; else dp[i][j] fmax(dp[i-1][j], dp[i][j-1]);C语言实现需要注意字符串索引从0开始int longestCommonSubsequence(char * text1, char * text2) { int m strlen(text1), n strlen(text2); int dp[m1][n1]; memset(dp, 0, sizeof(dp)); for (int i 1; i m; i) { for (int 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] fmax(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; }3.2 编辑距离问题另一个经典的字符串DP是编辑距离LeetCode 72状态转移更为复杂dp[i][j] min( dp[i-1][j] 1, // 删除 dp[i][j-1] 1, // 插入 dp[i-1][j-1] cost // 替换 );4. 区间DP与矩阵链乘法区间DP通常用于解决涉及区间划分的问题如矩阵链乘法、石子合并等。这类问题的特点是需要枚举区间长度和分割点。4.1 矩阵链乘法给定矩阵链A1×A2×...×An确定乘法顺序使标量乘法次数最少。状态定义dp[i][j] 表示计算Ai..j所需的最小乘法次数状态转移方程for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] p[i-1]*p[k]*p[j]); }实现时需要特别注意遍历顺序int matrixChainOrder(int p[], int n) { int dp[n][n]; memset(dp, 0, sizeof(dp)); for (int len 2; len n; len) { // 区间长度 for (int i 1; i n - len 1; i) { int j i len - 1; dp[i][j] INT_MAX; for (int k i; k j; k) { int cost dp[i][k] dp[k1][j] p[i-1]*p[k]*p[j]; if (cost dp[i][j]) dp[i][j] cost; } } } return dp[1][n-1]; }调试技巧打印dp表是调试区间DP最有效的方法。我在做LeetCode 1547时通过打印发现初始值设置错误节省了2小时调试时间。5. 状态机DP与股票买卖问题状态机DP通过定义多个状态及其转移条件来解决问题股票买卖系列是其典型应用。5.1 买卖股票的最佳时机以LeetCode 121为例最简单的状态定义dp[i][0] 第i天不持有股票的最大利润 dp[i][1] 第i天持有股票的最大利润状态转移dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]); dp[i][1] max(dp[i-1][1], -prices[i]);C实现可以优化空间复杂度到O(1)int maxProfit(int* prices, int pricesSize) { int dp0 0, dp1 -prices[0]; for (int i 1; i pricesSize; i) { dp0 fmax(dp0, dp1 prices[i]); dp1 fmax(dp1, -prices[i]); } return dp0; }5.2 冷冻期问题更复杂的状态机如LeetCode 309含冷冻期需要增加状态dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]); dp[i][1] max(dp[i-1][1], dp[i-2][0] - prices[i]);6. 树形DP与打家劫舍III树形动态规划需要在树上进行后序遍历典型问题是打家劫舍IIILeetCode 337。6.1 树形DP解法每个节点有两种状态选择当前节点不能选择子节点不选当前节点可以选择子节点状态转移struct { int selected; // 选当前节点的最大值 int notSelected; // 不选当前节点的最大值 } dfs(struct TreeNode* root) { if (!root) return (struct dp){0, 0}; struct dp l dfs(root-left); struct dp r dfs(root-right); int selected root-val l.notSelected r.notSelected; int notSelected fmax(l.selected, l.notSelected) fmax(r.selected, r.notSelected); return (struct dp){selected, notSelected}; }7. 数位DP与数字计数问题数位DP用于解决与数字各位相关的计数问题如计算区间内满足特定条件的数字个数。7.1 基本模板以LeetCode 233数字1的个数为例int countDigitOne(int n) { long long digit 1; int high n / 10, cur n % 10, low 0; int res 0; while (high ! 0 || cur ! 0) { if (cur 0) res high * digit; else if (cur 1) res high * digit low 1; else res (high 1) * digit; low cur * digit; cur high % 10; high / 10; digit * 10; } return res; }经验之谈数位DP的难点在于确定digit的边界条件。建议先在纸上模拟n10,100,1000等特殊情况我在面试中曾因此避免了一次错误解答。