动态规划算法深度解析：从背包九讲到LeetCode实战
动态规划算法深度解析：从背包九讲到LeetCode实战
目录
- 动态规划基础概念
- 背包问题详解
- 经典LeetCode题目分析
- 实现技巧与优化
- 总结与进阶
1. 动态规划基础概念
1.1 什么是动态规划？
动态规划（Dynamic Programming，简称DP）是一种算法设计技术，通过把原问题分解为相对简单的子问题，并存储子问题的解来避免重复计算，从而解决整体优化问题。
1.2 动态规划的核心要素
1.2.1 最优子结构
问题的最优解包含其子问题的最优解。
1.2.2 重叠子问题
在递归求解过程中，会重复计算相同的子问题。
1.2.3 状态转移方程
描述问题状态之间关系的数学表达式。
1.3 动态规划解题步骤
1. 确定dp数组（dp table）以及下标的含义2. 确定递推公式3. dp数组如何初始化4. 确定遍历顺序5. 举例推导dp数组2. 背包问题详解
背包问题是动态规划的经典问题类型，理解透彻背包问题对掌握动态规划至关重要。
背包九讲是计算机算法中经典的动态规划问题集合，主要解决不同类型的背包问题及其变种。这九个问题涵盖了几乎所有的背包问题变型，是动态规划学习的重要里程碑。
背包九讲概览
- 01背包问题：每个物品只能选或不选
- 完全背包问题：每个物品可以选无限次
- 多重背包问题：每个物品有固定数量限制
- 混合背包问题：混合多种背包类型
- 二维费用背包问题：物品有两个费用维度
- 分组背包问题：物品分组，每组只能选一个
- 有依赖的背包问题：物品间存在依赖关系
- 泛化物品背包问题：物品价值函数泛化
- 背包问题求方案数：求达到最优解的方案数
2.1 01背包问题
2.1.1 问题描述
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
2.1.2 状态定义
dp[i][j] = 前i个物品放入容量为j的背包中获得的最大价值2.1.3 状态转移方程
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])2.1.4 Java实现
public class ZeroOneKnapsack { /** * 01背包问题 - 二维数组版本 * @param weights 物品重量数组 * @param values 物品价值数组 * @param capacity 背包容量 * @return 最大价值 */ public int knapsack2D(int[] weights, int[] values, int capacity) { int n = weights.length; // dp[i][j]表示前i个物品放入容量为j的背包中获得的最大价值 int[][] dp = new int[n + 1][capacity + 1]; // 初始化：第0行和第0列都为0（已默认初始化） // 遍历物品 for (int i = 1; i <= n; i++) { // 遍历背包容量 for (int j = 1; j <= capacity; j++) { // 当前物品重量大于背包容量，无法放入 if (weights[i - 1] > j) { dp[i][j] = dp[i - 1][j]; } else { // 选择放入或不放入当前物品的最大价值 dp[i][j] = Math.max( dp[i - 1][j], // 不放入当前物品 dp[i - 1][j - weights[i - 1]] + values[i - 1] // 放入当前物品 ); } } } return dp[n][capacity]; } /** * 01背包问题 - 一维数组优化版本 * @param weights 物品重量数组 * @param values 物品价值数组 * @param capacity 背包容量 * @return 最大价值 */ public int knapsack1D(int[] weights, int[] values, int capacity) { int n = weights.length; // dp[j]表示容量为j的背包所能获得的最大价值 int[] dp = new int[capacity + 1]; // 遍历物品 for (int i = 0; i < n; i++) { // 从后向前遍历背包容量（重要！避免重复使用同一物品） for (int j = capacity; j >= weights[i]; j--) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); } } return dp[capacity]; } /** * 演示01背包问题的求解过程 */ public void demonstrateKnapsack() { int[] weights = {1, 3, 4}; int[] values = {15, 20, 30}; int capacity = 4; System.out.println(\"物品重量: \" + Arrays.toString(weights)); System.out.println(\"物品价值: \" + Arrays.toString(values)); System.out.println(\"背包容量: \" + capacity); int result = knapsack2D(weights, values, capacity); System.out.println(\"最大价值: \" + result); // 打印dp表格 printDPTable(weights, values, capacity); } private void printDPTable(int[] weights, int[] values, int capacity) { int n = weights.length; int[][] dp = new int[n + 1][capacity + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= capacity; j++) { if (weights[i - 1] > j) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]); } } } System.out.println(\"\\nDP表格:\"); System.out.print(\"容量\\\\物品\\t\"); for (int i = 0; i <= n; i++) { System.out.print(i + \"\\t\"); } System.out.println(); for (int j = 0; j <= capacity; j++) { System.out.print(j + \"\\t\\t\"); for (int i = 0; i <= n; i++) { System.out.print(dp[i][j] + \"\\t\"); } System.out.println(); } }}2.2 完全背包问题
2.2.1 问题描述
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
2.2.2 与01背包的区别
完全背包的特点是每种物品有无限件，可以重复选择。
2.2.3 Java实现
public class CompleteKnapsack { /** * 完全背包问题 * @param weights 物品重量数组 * @param values 物品价值数组 * @param capacity 背包容量 * @return 最大价值 */ public int completeKnapsack(int[] weights, int[] values, int capacity) { int n = weights.length; int[] dp = new int[capacity + 1]; // 遍历物品 for (int i = 0; i < n; i++) { // 从前向后遍历背包容量（重要！允许重复使用同一物品） for (int j = weights[i]; j <= capacity; j++) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); } } return dp[capacity]; } /** * 完全背包问题 - 二维数组版本（更容易理解） */ public int completeKnapsack2D(int[] weights, int[] values, int capacity) { int n = weights.length; int[][] dp = new int[n + 1][capacity + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= capacity; j++) { // 不选择当前物品 dp[i][j] = dp[i - 1][j]; // 选择当前物品（可以重复选择） if (j >= weights[i - 1]) { dp[i][j] = Math.max(dp[i][j], dp[i][j - weights[i - 1]] + values[i - 1]); } } } return dp[n][capacity]; }}2.3 多重背包问题
2.3.1 问题描述
有N种物品和一个容量为V的背包。第i种物品最多有num[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
2.3.2 Java实现
public class MultipleKnapsack { /** * 多重背包问题 - 二进制优化 * @param weights 物品重量数组 * @param values 物品价值数组 * @param nums 物品数量数组 * @param capacity 背包容量 * @return 最大价值 */ public int multipleKnapsack(int[] weights, int[] values, int[] nums, int capacity) { List<Integer> newWeights = new ArrayList<>(); List<Integer> newValues = new ArrayList<>(); // 二进制优化：将多重背包转化为01背包 for (int i = 0; i < weights.length; i++) { int num = nums[i]; for (int k = 1; k <= num; k *= 2) { int takeNum = Math.min(k, num); newWeights.add(weights[i] * takeNum); newValues.add(values[i] * takeNum); num -= takeNum; } } // 转化为01背包问题求解 int[] w = newWeights.stream().mapToInt(Integer::intValue).toArray(); int[] v = newValues.stream().mapToInt(Integer::intValue).toArray(); return knapsack01(w, v, capacity); } private int knapsack01(int[] weights, int[] values, int capacity) { int[] dp = new int[capacity + 1]; for (int i = 0; i < weights.length; i++) { for (int j = capacity; j >= weights[i]; j--) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); } } return dp[capacity]; }}2.4 混合背包问题
2.4.1 问题描述
有N种物品和一个容量为V的背包。这些物品有三种类型：
- 第一类：只能选0次或1次（01背包）
- 第二类：可以选无限次（完全背包）
- 第三类：最多选k次（多重背包）
求解将哪些物品装入背包可使价值总和最大。
2.4.2 Java实现
public class MixedKnapsack { // 物品类型枚举 enum ItemType { ZERO_ONE, // 01背包物品 COMPLETE, // 完全背包物品 MULTIPLE // 多重背包物品 } static class Item { int weight; int value; int count; // 数量限制，-1表示无限，1表示01背包 ItemType type; public Item(int weight, int value, ItemType type, int count) { this.weight = weight; this.value = value; this.type = type; this.count = count; } } /** * 混合背包问题 * @param items 物品数组 * @param capacity 背包容量 * @return 最大价值 */ public int mixedKnapsack(Item[] items, int capacity) { int[] dp = new int[capacity + 1]; for (Item item : items) { if (item.type == ItemType.ZERO_ONE) { // 01背包处理：从后向前 for (int j = capacity; j >= item.weight; j--) { dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value); } } else if (item.type == ItemType.COMPLETE) { // 完全背包处理：从前向后 for (int j = item.weight; j <= capacity; j++) { dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value); } } else if (item.type == ItemType.MULTIPLE) { // 多重背包处理：二进制优化 multipleKnapsackProcess(dp, item.weight, item.value, item.count, capacity); } } return dp[capacity]; } private void multipleKnapsackProcess(int[] dp, int weight, int value, int count, int capacity) { int k = 1; while (k <= count) { int w = k * weight; int v = k * value; // 01背包处理 for (int j = capacity; j >= w; j--) { dp[j] = Math.max(dp[j], dp[j - w] + v); } count -= k; k *= 2; } if (count > 0) { int w = count * weight; int v = count * value; for (int j = capacity; j >= w; j--) { dp[j] = Math.max(dp[j], dp[j - w] + v); } } }}2.5 二维费用背包问题
2.5.1 问题描述
有N件物品和一个背包，背包有两个容量限制：重量限制V和体积限制U。第i件物品的重量是w[i]，体积是u[i]，价值是val[i]。求解将哪些物品装入背包可使价值总和最大。
2.5.2 Java实现
public class TwoDimensionKnapsack { /** * 二维费用背包问题 * @param weights 物品重量数组 * @param volumes 物品体积数组 * @param values 物品价值数组 * @param weightLimit 重量限制 * @param volumeLimit 体积限制 * @return 最大价值 */ public int twoDimensionKnapsack(int[] weights, int[] volumes, int[] values, int weightLimit, int volumeLimit) { // dp[i][j]表示重量不超过i，体积不超过j时的最大价值 int[][] dp = new int[weightLimit + 1][volumeLimit + 1]; int n = weights.length; for (int k = 0; k < n; k++) { // 从后向前遍历（01背包） for (int i = weightLimit; i >= weights[k]; i--) { for (int j = volumeLimit; j >= volumes[k]; j--) { dp[i][j] = Math.max(dp[i][j], dp[i - weights[k]][j - volumes[k]] + values[k]); } } } return dp[weightLimit][volumeLimit]; } /** * 一维数组优化版本 */ public int twoDimensionKnapsackOptimized(int[] weights, int[] volumes, int[] values,int weightLimit, int volumeLimit) { // 使用一维数组，但需要临时存储 int[][] dp = new int[weightLimit + 1][volumeLimit + 1]; for (int k = 0; k < weights.length; k++) { for (int i = weightLimit; i >= weights[k]; i--) { for (int j = volumeLimit; j >= volumes[k]; j--) { dp[i][j] = Math.max(dp[i][j], dp[i - weights[k]][j - volumes[k]] + values[k]); } } } return dp[weightLimit][volumeLimit]; } /** * 演示二维费用背包 */ public void demonstrateTwoDimensionKnapsack() { int[] weights = {2, 1, 3, 2}; int[] volumes = {1, 1, 3, 2}; int[] values = {3, 2, 4, 2}; int weightLimit = 5; int volumeLimit = 4; System.out.println(\"物品重量: \" + Arrays.toString(weights)); System.out.println(\"物品体积: \" + Arrays.toString(volumes)); System.out.println(\"物品价值: \" + Arrays.toString(values)); System.out.println(\"重量限制: \" + weightLimit); System.out.println(\"体积限制: \" + volumeLimit); int result = twoDimensionKnapsack(weights, volumes, values, weightLimit, volumeLimit); System.out.println(\"最大价值: \" + result); }}2.6 分组背包问题
2.6.1 问题描述
有N组物品和一个容量为V的背包。第i组物品有k[i]个，每组中的物品最多只能选择一个。每件物品有重量w[i][j]和价值v[i][j]。求解将哪些物品装入背包可使价值总和最大。
2.6.2 Java实现
public class GroupKnapsack { static class ItemGroup { List<Item> items; public ItemGroup() { this.items = new ArrayList<>(); } public void addItem(int weight, int value) { items.add(new Item(weight, value)); } } static class Item { int weight, value; public Item(int weight, int value) { this.weight = weight; this.value = value; } } /** * 分组背包问题 * @param groups 物品组数组 * @param capacity 背包容量 * @return 最大价值 */ public int groupKnapsack(List<ItemGroup> groups, int capacity) { int[] dp = new int[capacity + 1]; // 遍历每个组 for (ItemGroup group : groups) { // 从后向前遍历容量（保证每组最多选一个） for (int j = capacity; j >= 0; j--) { // 尝试该组中的每个物品 for (Item item : group.items) { if (j >= item.weight) { dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value); } } } } return dp[capacity]; } /** * 二维数组版本（更易理解） */ public int groupKnapsack2D(List<ItemGroup> groups, int capacity) { int groupCount = groups.size(); int[][] dp = new int[groupCount + 1][capacity + 1]; for (int i = 1; i <= groupCount; i++) { ItemGroup group = groups.get(i - 1); for (int j = 0; j <= capacity; j++) { // 不选择当前组的任何物品 dp[i][j] = dp[i - 1][j]; // 尝试选择当前组中的每个物品 for (Item item : group.items) { if (j >= item.weight) { dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - item.weight] + item.value); } } } } return dp[groupCount][capacity]; } /** * 演示分组背包 */ public void demonstrateGroupKnapsack() { List<ItemGroup> groups = new ArrayList<>(); // 第一组物品 ItemGroup group1 = new ItemGroup(); group1.addItem(1, 2); // 重量1，价值2 group1.addItem(2, 3); // 重量2，价值3 groups.add(group1); // 第二组物品 ItemGroup group2 = new ItemGroup(); group2.addItem(3, 4); // 重量3，价值4 group2.addItem(4, 5); // 重量4，价值5 groups.add(group2); int capacity = 5; System.out.println(\"分组背包演示:\"); System.out.println(\"第一组物品: (1,2), (2,3)\"); System.out.println(\"第二组物品: (3,4), (4,5)\"); System.out.println(\"背包容量: \" + capacity); int result = groupKnapsack(groups, capacity); System.out.println(\"最大价值: \" + result); }}2.7 有依赖的背包问题
2.7.1 问题描述
有N件物品和一个容量为V的背包。物品之间有依赖关系，即选择某些物品必须先选择它们的\"主件\"。每件物品有重量w[i]和价值v[i]。求解将哪些物品装入背包可使价值总和最大。
2.7.2 Java实现
public class DependentKnapsack { static class TreeNode { int weight, value; List<TreeNode> children; public TreeNode(int weight, int value) { this.weight = weight; this.value = value; this.children = new ArrayList<>(); } public void addChild(TreeNode child) { this.children.add(child); } } /** * 有依赖的背包问题 - 树形DP * @param root 依赖树的根节点 * @param capacity 背包容量 * @return 最大价值 */ public int dependentKnapsack(TreeNode root, int capacity) { return dfs(root, capacity)[capacity]; } /** * DFS求解子树的背包问题 * @param node 当前节点 * @param capacity 容量 * @return dp数组，dp[i]表示容量为i时当前子树的最大价值 */ private int[] dfs(TreeNode node, int capacity) { int[] dp = new int[capacity + 1]; if (node == null) return dp; // 如果容量不足以放入当前物品，返回全0数组 if (capacity < node.weight) { return dp; } // 初始化：选择当前物品 for (int i = node.weight; i <= capacity; i++) { dp[i] = node.value; } // 处理每个子节点 for (TreeNode child : node.children) { int[] childDp = dfs(child, capacity); // 将子节点的结果合并到当前节点 // 从后向前遍历，类似于分组背包 for (int i = capacity; i >= node.weight; i--) { for (int j = 0; j <= i - node.weight; j++) { dp[i] = Math.max(dp[i], dp[i - j] + childDp[j]); } } } return dp; } /** * 另一种实现：基于分组背包的思路 */ public int dependentKnapsackAlternative(TreeNode root, int capacity) { List<List<TreeNode>> groups = new ArrayList<>(); buildGroups(root, groups); int[] dp = new int[capacity + 1]; for (List<TreeNode> group : groups) { for (int j = capacity; j >= 0; j--) { for (TreeNode item : group) { if (j >= item.weight) { dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value); } } } } return dp[capacity]; } private void buildGroups(TreeNode node, List<List<TreeNode>> groups) { if (node == null) return; List<TreeNode> group = new ArrayList<>(); generateCombinations(node, 0, 0, group, groups); for (TreeNode child : node.children) { buildGroups(child, groups); } } private void generateCombinations(TreeNode node, int totalWeight, int totalValue, List<TreeNode> current, List<List<TreeNode>> groups) { // 添加当前组合（包含根节点） TreeNode combination = new TreeNode(totalWeight + node.weight, totalValue + node.value); List<TreeNode> newGroup = new ArrayList<>(current); newGroup.add(combination); groups.add(newGroup); // 递归处理子节点的组合 for (TreeNode child : node.children) { generateCombinations(child, totalWeight + node.weight, totalValue + node.value, newGroup, groups); } }}2.8 泛化物品背包问题
2.8.1 问题描述
泛化物品是这样一种物品：它并没有固定的费用和价值，而是有一个费用函数c(k)和价值函数w(k)，表示选择k个该物品时的费用和价值。
2.8.2 Java实现
public class GeneralizedKnapsack { interface ValueFunction { int getValue(int count); } interface CostFunction { int getCost(int count); } static class GeneralizedItem { ValueFunction valueFunc; CostFunction costFunc; int maxCount; public GeneralizedItem(ValueFunction valueFunc, CostFunction costFunc, int maxCount) { this.valueFunc = valueFunc; this.costFunc = costFunc; this.maxCount = maxCount; } } /** * 泛化物品背包问题 * @param items 泛化物品数组 * @param capacity 背包容量 * @return 最大价值 */ public int generalizedKnapsack(GeneralizedItem[] items, int capacity) { int[] dp = new int[capacity + 1]; for (GeneralizedItem item : items) { // 为每个泛化物品生成所有可能的选择 List<int[]> choices = new ArrayList<>(); for (int k = 0; k <= item.maxCount; k++) { int cost = item.costFunc.getCost(k); int value = item.valueFunc.getValue(k); if (cost <= capacity) { choices.add(new int[]{cost, value}); } } // 将泛化物品转化为分组背包问题 for (int j = capacity; j >= 0; j--) { for (int[] choice : choices) { int cost = choice[0]; int value = choice[1]; if (j >= cost) { dp[j] = Math.max(dp[j], dp[j - cost] + value); } } } } return dp[capacity]; } /** * 演示泛化物品背包 */ public void demonstrateGeneralizedKnapsack() { GeneralizedItem[] items = new GeneralizedItem[2]; // 第一个泛化物品：选择k个时，费用为k，价值为k*k items[0] = new GeneralizedItem( k -> k * k, // 价值函数 k -> k, // 费用函数 5 // 最大数量 ); // 第二个泛化物品：选择k个时，费用为2*k，价值为3*k items[1] = new GeneralizedItem( k -> 3 * k, // 价值函数 k -> 2 * k, // 费用函数 3 // 最大数量 ); int capacity = 10; System.out.println(\"泛化物品背包演示:\"); System.out.println(\"物品1: 选择k个时费用为k，价值为k²，最大数量5\"); System.out.println(\"物品2: 选择k个时费用为2k，价值为3k，最大数量3\"); System.out.println(\"背包容量: \" + capacity); int result = generalizedKnapsack(items, capacity); System.out.println(\"最大价值: \" + result); }}2.9 背包问题求方案数
2.9.1 问题描述
在背包问题的基础上，不仅要求出最大价值，还要求出达到最大价值的方案总数。
2.9.2 Java实现
public class KnapsackSolutionCount { /** * 01背包求方案数 * @param weights 物品重量数组 * @param values 物品价值数组 * @param capacity 背包容量 * @return [最大价值, 方案数] */ public int[] knapsackWithCount(int[] weights, int[] values, int capacity) { int n = weights.length; int[] dp = new int[capacity + 1]; // 最大价值 int[] count = new int[capacity + 1]; // 方案数 // 初始化 Arrays.fill(count, 1); // 什么都不选也是一种方案 for (int i = 0; i < n; i++) { for (int j = capacity; j >= weights[i]; j--) { int newValue = dp[j - weights[i]] + values[i]; if (newValue > dp[j]) { // 发现更优解，更新最大价值和方案数 dp[j] = newValue; count[j] = count[j - weights[i]]; } else if (newValue == dp[j]) { // 发现同样优的解，累加方案数 count[j] += count[j - weights[i]]; } } } return new int[]{dp[capacity], count[capacity]}; } /** * 完全背包求方案数 * @param weights 物品重量数组 * @param values 物品价值数组 * @param capacity 背包容量 * @return [最大价值, 方案数] */ public int[] completeKnapsackWithCount(int[] weights, int[] values, int capacity) { int[] dp = new int[capacity + 1]; int[] count = new int[capacity + 1]; Arrays.fill(count, 1); for (int i = 0; i < weights.length; i++) { for (int j = weights[i]; j <= capacity; j++) { int newValue = dp[j - weights[i]] + values[i]; if (newValue > dp[j]) { dp[j] = newValue; count[j] = count[j - weights[i]]; } else if (newValue == dp[j]) { count[j] += count[j - weights[i]]; } } } return new int[]{dp[capacity], count[capacity]}; } /** * 求具体方案（路径回溯） * @param weights 物品重量数组 * @param values 物品价值数组 * @param capacity 背包容量 * @return 最优方案的物品选择情况 */ public List<Integer> getOptimalSolution(int[] weights, int[] values, int capacity) { int n = weights.length; int[][] dp = new int[n + 1][capacity + 1]; // 构建DP表 for (int i = 1; i <= n; i++) { for (int j = 1; j <= capacity; j++) { if (weights[i - 1] > j) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]); } } } // 回溯找出具体方案 List<Integer> solution = new ArrayList<>(); int i = n, j = capacity; while (i > 0 && j > 0) { if (dp[i][j] != dp[i - 1][j]) { // 选择了第i个物品 solution.add(i - 1); j -= weights[i - 1]; } i--; } Collections.reverse(solution); return solution; } /** * 演示背包问题求方案数 */ public void demonstrateKnapsackCount() { int[] weights = {2, 1, 3, 2}; int[] values = {1, 1, 3, 2}; int capacity = 5; System.out.println(\"背包问题求方案数演示:\"); System.out.println(\"物品重量: \" + Arrays.toString(weights)); System.out.println(\"物品价值: \" + Arrays.toString(values)); System.out.println(\"背包容量: \" + capacity); int[] result = knapsackWithCount(weights, values, capacity); System.out.println(\"最大价值: \" + result[0]); System.out.println(\"方案数: \" + result[1]); List<Integer> solution = getOptimalSolution(weights, values, capacity); System.out.println(\"一种最优方案: \" + solution); }}3. 经典LeetCode题目分析
3.1 LeetCode 322: 零钱兑换
3.1.1 问题描述
给定不同面额的硬币coins和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
3.1.2 分析
这是一个典型的完全背包问题的变种，求最少硬币数量。
3.1.3 Java解法
public class CoinChange { /** * LeetCode 322: 零钱兑换 * @param coins 硬币面额数组 * @param amount 目标金额 * @return 最少硬币数量，无法凑成返回-1 */ public int coinChange(int[] coins, int amount) { // dp[i]表示凑成金额i所需的最少硬币数量 int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); // 初始化为一个不可能的大值 dp[0] = 0; // 凑成金额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]; } /** * 演示求解过程 */ public void demonstrateCoinChange() { int[] coins = {1, 3, 4}; int amount = 6; System.out.println(\"硬币面额: \" + Arrays.toString(coins)); System.out.println(\"目标金额: \" + amount); // 详细求解过程 int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0; System.out.println(\"\\n求解过程:\"); System.out.println(\"金额\\t最少硬币数\"); System.out.println(\"0\\t\" + dp[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); } } System.out.println(i + \"\\t\" + (dp[i] > amount ? \"∞\" : dp[i])); } System.out.println(\"\\n结果: \" + (dp[amount] > amount ? -1 : dp[amount])); }}3.2 LeetCode 518: 零钱兑换II
3.2.1 问题描述
给定不同面额的硬币和一个总金额，写出函数来计算可以凑成总金额的硬币组合数。
3.2.2 Java解法
public class CoinChangeII { /** * LeetCode 518: 零钱兑换II * @param amount 目标金额 * @param coins 硬币面额数组 * @return 组合数 */ public int change(int amount, int[] coins) { // dp[i]表示凑成金额i的组合数 int[] dp = new int[amount + 1]; dp[0] = 1; // 凑成金额0有1种方法（不选任何硬币） // 遍历硬币（外层循环硬币，内层循环金额，避免重复计算） for (int coin : coins) { // 遍历金额 for (int i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount]; } /** * 演示组合数计算过程 */ public void demonstrateChange() { int amount = 5; int[] coins = {1, 2, 5}; System.out.println(\"目标金额: \" + amount); System.out.println(\"硬币面额: \" + Arrays.toString(coins)); int[] dp = new int[amount + 1]; dp[0] = 1; System.out.println(\"\\n计算过程:\"); System.out.println(\"初始状态: \" + Arrays.toString(dp)); for (int coin : coins) { System.out.println(\"\\n使用硬币 \" + coin + \":\"); for (int i = coin; i <= amount; i++) { int oldValue = dp[i]; dp[i] += dp[i - coin]; System.out.println(\"dp[\" + i + \"] = \" + oldValue + \" + dp[\" + (i - coin) + \"] = \" + dp[i]); } System.out.println(\"当前状态: \" + Arrays.toString(dp)); } System.out.println(\"\\n最终组合数: \" + dp[amount]); }}3.3 LeetCode 416: 分割等和子集
3.3.1 问题描述
给定一个只包含正整数的非空数组，是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
3.3.2 分析
这是一个01背包问题的变种，目标是判断是否能找到和为sum/2的子集。
3.3.3 Java解法
public class PartitionEqualSubsetSum { /** * LeetCode 416: 分割等和子集 * @param nums 数组 * @return 是否可以分割 */ public boolean canPartition(int[] nums) { int sum = Arrays.stream(nums).sum(); // 如果总和为奇数，无法分割 if (sum % 2 != 0) { return false; } int target = sum / 2; // dp[i]表示是否可以凑成和为i boolean[] dp = new boolean[target + 1]; dp[0] = true; // 和为0总是可以凑成（不选任何数） for (int num : nums) { // 从后向前遍历（01背包） for (int j = target; j >= num; j--) { dp[j] = dp[j] || dp[j - num]; } } return dp[target]; } /** * 演示分割过程 */ public void demonstratePartition() { int[] nums = {1, 5, 11, 5}; System.out.println(\"数组: \" + Arrays.toString(nums)); System.out.println(\"数组和: \" + Arrays.stream(nums).sum()); int sum = Arrays.stream(nums).sum(); if (sum % 2 != 0) { System.out.println(\"数组和为奇数，无法分割\"); return; } int target = sum / 2; System.out.println(\"目标和: \" + target); boolean[] dp = new boolean[target + 1]; dp[0] = true; System.out.println(\"\\n计算过程:\"); System.out.print(\"初始状态: \"); printBooleanArray(dp); for (int num : nums) { System.out.println(\"\\n处理数字 \" + num + \":\"); for (int j = target; j >= num; j--) { boolean oldValue = dp[j]; dp[j] = dp[j] || dp[j - num]; if (dp[j] != oldValue) { System.out.println(\"dp[\" + j + \"] = true (通过 dp[\" + (j - num) + \"] + \" + num + \")\"); } } System.out.print(\"当前状态: \"); printBooleanArray(dp); } System.out.println(\"\\n结果: \" + dp[target]); } private void printBooleanArray(boolean[] arr) { System.out.print(\"[\"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] ? \"T\" : \"F\"); if (i < arr.length - 1) System.out.print(\", \"); } System.out.println(\"]\"); }}3.4 LeetCode 494: 目标和
3.4.1 问题描述
给定一个非负整数数组和一个目标数S，为数组中的每个整数前添加’+‘或’-\'，计算有多少种添加符号的方法使得数组总和等于目标数S。
3.4.2 分析
可以转化为01背包问题：将数组分为两部分P（正数）和N（负数），有P - N = S且P + N = sum，可得P = (S + sum) / 2。
3.4.3 Java解法
public class TargetSum { /** * LeetCode 494: 目标和 * @param nums 数组 * @param S 目标和 * @return 方法数 */ public int findTargetSumWays(int[] nums, int S) { int sum = Arrays.stream(nums).sum(); // 检查是否有解 if (S > sum || S < -sum || (S + sum) % 2 != 0) { return 0; } int target = (S + sum) / 2; // dp[i]表示凑成和为i的方法数 int[] dp = new int[target + 1]; dp[0] = 1; // 凑成和为0有1种方法 for (int num : nums) { for (int j = target; j >= num; j--) { dp[j] += dp[j - num]; } } return dp[target]; } /** * 演示计算过程 */ public void demonstrateTargetSum() { int[] nums = {1, 1, 1, 1, 1}; int S = 3; System.out.println(\"数组: \" + Arrays.toString(nums)); System.out.println(\"目标和: \" + S); int sum = Arrays.stream(nums).sum(); System.out.println(\"数组总和: \" + sum); if (S > sum || S < -sum || (S + sum) % 2 != 0) { System.out.println(\"无解\"); return; } int target = (S + sum) / 2; System.out.println(\"转化后的目标: \" + target); int[] dp = new int[target + 1]; dp[0] = 1; System.out.println(\"\\n计算过程:\"); System.out.println(\"初始状态: \" + Arrays.toString(dp)); for (int num : nums) { System.out.println(\"\\n处理数字 \" + num + \":\"); for (int j = target; j >= num; j--) { int oldValue = dp[j]; dp[j] += dp[j - num]; if (dp[j] != oldValue) { System.out.println(\"dp[\" + j + \"] = \" + oldValue + \" + dp[\" + (j - num) + \"] = \" + dp[j]); } } System.out.println(\"当前状态: \" + Arrays.toString(dp)); } System.out.println(\"\\n最终结果: \" + dp[target]); }}3.5 LeetCode 300: 最长递增子序列
3.5.1 问题描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
3.5.2 Java解法
public class LongestIncreasingSubsequence { /** * LeetCode 300: 最长递增子序列 - 动态规划解法 * @param nums 数组 * @return 最长递增子序列长度 */ public int lengthOfLIS(int[] nums) { if (nums.length == 0) return 0; // dp[i]表示以nums[i]结尾的最长递增子序列长度 int[] dp = new int[nums.length]; Arrays.fill(dp, 1); // 每个元素自身构成长度为1的子序列 int maxLength = 1; for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } maxLength = Math.max(maxLength, dp[i]); } return maxLength; } /** * 二分查找优化版本 - O(nlogn) */ public int lengthOfLISOptimized(int[] nums) { if (nums.length == 0) return 0; // tails[i]表示长度为i+1的递增子序列的最小尾部元素 int[] tails = new int[nums.length]; int size = 0; for (int num : nums) { int left = 0, right = size; // 二分查找第一个大于等于num的位置 while (left < right) { int mid = left + (right - left) / 2; if (tails[mid] < num) { left = mid + 1; } else { right = mid; } } tails[left] = num; if (left == size) size++; } return size; } /** * 演示LIS计算过程 */ public void demonstrateLIS() { int[] nums = {10, 9, 2, 5, 3, 7, 101, 18}; System.out.println(\"数组: \" + Arrays.toString(nums)); int[] dp = new int[nums.length]; Arrays.fill(dp, 1); System.out.println(\"\\n动态规划过程:\"); System.out.println(\"索引\\t元素\\tdp值\\t说明\"); System.out.println(\"0\\t\" + nums[0] + \"\\t\" + dp[0] + \"\\t初始值\"); for (int i = 1; i < nums.length; i++) { StringBuilder explanation = new StringBuilder(); for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { int newLength = dp[j] + 1; if (newLength > dp[i]) { dp[i] = newLength; explanation.append(\"从位置\").append(j).append(\"扩展,\"); } } } System.out.println(i + \"\\t\" + nums[i] + \"\\t\" + dp[i] + \"\\t\" + (explanation.length() > 0 ? explanation.toString() : \"无法扩展\")); } int result = Arrays.stream(dp).max().orElse(0); System.out.println(\"\\nDP数组: \" + Arrays.toString(dp)); System.out.println(\"最长递增子序列长度: \" + result); }}4. 实现技巧与优化
4.1 空间优化技巧
4.1.1 滚动数组
当dp[i]只依赖于dp[i-1]时，可以使用滚动数组优化空间复杂度。
public class SpaceOptimization { /** * 斐波那契数列 - 滚动数组优化 */ public int fibonacci(int n) { if (n <= 1) return n; int prev2 = 0, prev1 = 1; for (int i = 2; i <= n; i++) { int curr = prev1 + prev2; prev2 = prev1; prev1 = curr; } return prev1; } /** * 路径数问题 - 一维数组优化 */ public int uniquePaths(int m, int n) { int[] dp = new int[n]; Arrays.fill(dp, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j - 1]; } } return dp[n - 1]; }}4.2 遍历顺序的重要性
4.2.1 背包问题中的遍历顺序
public class TraversalOrder { /** * 01背包：必须从后向前遍历 */ public int knapsack01(int[] weights, int[] values, int capacity) { int[] dp = new int[capacity + 1]; for (int i = 0; i < weights.length; i++) { // 从后向前遍历，避免重复使用同一物品 for (int j = capacity; j >= weights[i]; j--) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); } } return dp[capacity]; } /** * 完全背包：必须从前向后遍历 */ public int completeKnapsack(int[] weights, int[] values, int capacity) { int[] dp = new int[capacity + 1]; for (int i = 0; i < weights.length; i++) { // 从前向后遍历，允许重复使用同一物品 for (int j = weights[i]; j <= capacity; j++) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); } } return dp[capacity]; } /** * 组合数问题：外层遍历物品，内层遍历容量 */ public int combinationSum4Wrong(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; // 错误的遍历顺序：会产生重复的组合 for (int i = 1; i <= target; i++) { for (int num : nums) { if (i >= num) { dp[i] += dp[i - num]; } } } return dp[target]; } /** * 排列数问题：外层遍历容量，内层遍历物品 */ public int combinationSum4Correct(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; // 正确的遍历顺序：产生排列而非组合 for (int i = 1; i <= target; i++) { for (int num : nums) { if (i >= num) { dp[i] += dp[i - num]; } } } return dp[target]; }}4.3 状态压缩与位运算
public class StateCompression { /** * 旅行商问题 - 状态压缩DP */ public int tsp(int[][] dist) { int n = dist.length; int[][] dp = new int[1 << n][n]; // 初始化 for (int[] row : dp) { Arrays.fill(row, Integer.MAX_VALUE); } dp[1][0] = 0; // 从城市0开始 for (int mask = 1; mask < (1 << n); mask++) { for (int u = 0; u < n; u++) { if ((mask & (1 << u)) == 0 || dp[mask][u] == Integer.MAX_VALUE) { continue; } for (int v = 0; v < n; v++) { if (mask & (1 << v)) continue; int newMask = mask | (1 << v); dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + dist[u][v]); } } } int result = Integer.MAX_VALUE; for (int i = 1; i < n; i++) { if (dp[(1 << n) - 1][i] != Integer.MAX_VALUE) { result = Math.min(result, dp[(1 << n) - 1][i] + dist[i][0]); } } return result; }}5. 总结与进阶
5.1 动态规划的思维模式
- 定义状态：明确dp数组的含义
- 找出转移：确定状态之间的关系
- 设定边界：确定初始状态
- 确定顺序：选择正确的计算顺序
- 优化空间：在可能的情况下优化空间复杂度
5.2 常见错误与调试技巧
5.2.1 常见错误
- 状态定义不清晰
- 转移方程错误
- 初始化不正确
- 遍历顺序错误
- 边界条件处理不当
5.2.2 调试技巧
public class DebugTips { /** * 调试动态规划的通用方法 */ public void debugDP() { // 1. 打印dp数组的变化过程 // 2. 验证小规模测试用例 // 3. 检查边界条件 // 4. 确认状态转移的正确性 } /** * 可视化dp表格 */ public void printDPTable(int[][] dp) { System.out.println(\"DP表格:\"); for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[i].length; j++) { System.out.printf(\"%4d\", dp[i][j]); } System.out.println(); } }}5.3 进阶话题
5.3.1 概率DP
处理概率相关的动态规划问题。
5.3.2 数位DP
处理数位相关的计数问题。
5.3.3 树形DP
在树结构上进行动态规划。
5.3.4 区间DP
处理区间相关的优化问题。
5.4 推荐练习题目
初级题目
- LeetCode 70: 爬楼梯
- LeetCode 198: 打家劫舍
- LeetCode 53: 最大子序和
中级题目
- LeetCode 121: 买卖股票的最佳时机
- LeetCode 322: 零钱兑换
- LeetCode 300: 最长递增子序列
高级题目
- LeetCode 312: 戳气球
- LeetCode 1000: 合并石头的最低成本
- LeetCode 87: 扰乱字符串
结语
动态规划是算法设计中的重要思想，掌握其核心思维模式和实现技巧对于解决复杂的优化问题至关重要。通过深入理解背包问题的各种变型和经典LeetCode题目的解法，我们可以建立起完整的动态规划知识体系。
记住，动态规划的精髓在于：
- 最优子结构：问题的最优解包含子问题的最优解
- 重叠子问题：避免重复计算相同的子问题
- 状态转移：明确状态之间的转移关系
通过大量的练习和思考，你将能够熟练运用动态规划解决各种复杂的算法问题。
本文详细分析了动态规划的核心概念、背包问题的各种变型以及经典LeetCode题目的解法，希望能帮助读者深入理解并掌握动态规划算法。
