13.4 动态规划
面试重要程度：⭐⭐⭐⭐⭐
常见提问方式： "设计DP状态转移方程" "优化空间复杂度" "背包问题变种"
预计阅读时间：50分钟
🎯 动态规划基础
DP解题框架
/**
* 动态规划解题框架
*/
public class DynamicProgrammingFramework {
/**
* DP解题步骤：
* 1. 确定状态定义
* 2. 找出状态转移方程
* 3. 确定初始状态
* 4. 确定计算顺序
* 5. 优化空间复杂度（可选）
*/
/**
* 斐波那契数列 - DP入门
* LeetCode 509: Fibonacci Number
*/
public int fib(int n) {
if (n <= 1) return n;
// 状态定义：dp[i]表示第i个斐波那契数
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];
}
/**
* 空间优化版本
*/
public int fibOptimized(int n) {
if (n <= 1) return n;
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
/**
* 爬楼梯
* LeetCode 70: Climbing Stairs
*/
public int climbStairs(int n) {
if (n <= 2) return n;
// dp[i]表示爬到第i阶的方法数
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
🎒 背包问题系列
0-1背包问题
/**
* 背包问题经典实现
*/
public class KnapsackProblems {
/**
* 0-1背包问题
* 每个物品只能选择一次
*/
public int knapsack01(int[] weights, int[] values, int capacity) {
int n = weights.length;
// dp[i][w]表示前i个物品，背包容量为w时的最大价值
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
// 不选择第i个物品
dp[i][w] = dp[i - 1][w];
// 选择第i个物品（如果能放下）
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[n][capacity];
}
/**
* 0-1背包空间优化版本
*/
public int knapsack01Optimized(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 w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
/**
* 分割等和子集
* LeetCode 416: Partition Equal Subset Sum
*/
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
// 如果总和为奇数，无法分割
if (sum % 2 != 0) return false;
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true; // 和为0总是可能的
for (int num : nums) {
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
/**
* 目标和
* LeetCode 494: Target Sum
*/
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
// 检查是否可能达到目标
if (target > sum || target < -sum || (sum + target) % 2 != 0) {
return 0;
}
int positive = (sum + target) / 2;
return subsetSum(nums, positive);
}
private int subsetSum(int[] nums, int target) {
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 class UnboundedKnapsack {
/**
* 完全背包问题
* 每个物品可以选择无限次
*/
public int unboundedKnapsack(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 w = weights[i]; w <= capacity; w++) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
/**
* 零钱兑换
* LeetCode 322: Coin Change
*/
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 (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
/**
* 零钱兑换II
* LeetCode 518: Coin Change 2
*/
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];
}
/**
* 组合总和IV
* LeetCode 377: Combination Sum IV
*/
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
// 注意：这里是先遍历target，再遍历nums
// 因为要考虑不同顺序的组合
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
📈 最长子序列问题
子序列DP
/**
* 最长子序列问题
*/
public class LongestSubsequenceProblems {
/**
* 最长递增子序列
* LeetCode 300: Longest Increasing Subsequence
*/
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[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
/**
* 最长递增子序列优化版本（二分查找）
* 时间复杂度：O(n log n)
*/
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;
}
/**
* 最长公共子序列
* LeetCode 1143: Longest Common Subsequence
*/
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
// dp[i][j]表示text1[0...i-1]和text2[0...j-1]的最长公共子序列长度
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];
}
/**
* 最长回文子序列
* LeetCode 516: Longest Palindromic Subsequence
*/
public int longestPalindromeSubseq(String s) {
int n = s.length();
// dp[i][j]表示s[i...j]的最长回文子序列长度
int[][] dp = new int[n][n];
// 单个字符的回文长度为1
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 按长度递增的顺序填表
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
/**
* 编辑距离
* LeetCode 72: Edit Distance
*/
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
// dp[i][j]表示word1[0...i-1]转换为word2[0...j-1]的最小操作数
int[][] dp = new int[m + 1][n + 1];
// 初始化边界条件
for (int i = 0; i <= m; i++) {
dp[i][0] = i; // 删除i个字符
}
for (int j = 0; j <= n; j++) {
dp[0][j] = 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] = Math.min(
Math.min(dp[i - 1][j] + 1, // 删除
dp[i][j - 1] + 1), // 插入
dp[i - 1][j - 1] + 1 // 替换
);
}
}
}
return dp[m][n];
}
}
💰 股票买卖问题
股票交易DP
/**
* 股票买卖问题系列
*/
public class StockTradingProblems {
/**
* 买卖股票的最佳时机
* LeetCode 121: Best Time to Buy and Sell Stock
*/
public int maxProfit(int[] prices) {
if (prices.length == 0) return 0;
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return maxProfit;
}
/**
* 买卖股票的最佳时机II
* LeetCode 122: Best Time to Buy and Sell Stock II
*/
public int maxProfitII(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
/**
* 买卖股票的最佳时机III
* LeetCode 123: Best Time to Buy and Sell Stock III
*/
public int maxProfitIII(int[] prices) {
if (prices.length == 0) return 0;
// 定义四个状态
int buy1 = -prices[0]; // 第一次买入后的最大利润
int sell1 = 0; // 第一次卖出后的最大利润
int buy2 = -prices[0]; // 第二次买入后的最大利润
int sell2 = 0; // 第二次卖出后的最大利润
for (int i = 1; i < prices.length; i++) {
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}
/**
* 买卖股票的最佳时机IV
* LeetCode 188: Best Time to Buy and Sell Stock IV
*/
public int maxProfitIV(int k, int[] prices) {
if (prices.length == 0) return 0;
int n = prices.length;
// 如果k足够大，相当于可以无限次交易
if (k >= n / 2) {
int profit = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
// dp[i][j]表示第i次交易后的最大利润
// j=0表示买入，j=1表示卖出
int[][] dp = new int[k + 1][2];
for (int i = 0; i <= k; i++) {
dp[i][0] = -prices[0]; // 买入状态
dp[i][1] = 0; // 卖出状态
}
for (int i = 1; i < n; i++) {
for (int j = k; j >= 1; j--) {
dp[j][1] = Math.max(dp[j][1], dp[j][0] + prices[i]);
dp[j][0] = Math.max(dp[j][0], dp[j - 1][1] - prices[i]);
}
}
return dp[k][1];
}
/**
* 买卖股票的最佳时机含冷冻期
* LeetCode 309: Best Time to Buy and Sell Stock with Cooldown
*/
public int maxProfitWithCooldown(int[] prices) {
if (prices.length <= 1) return 0;
int n = prices.length;
// 定义三个状态
int[] hold = new int[n]; // 持有股票
int[] sold = new int[n]; // 卖出股票（冷冻期）
int[] rest = new int[n]; // 休息状态
hold[0] = -prices[0];
sold[0] = 0;
rest[0] = 0;
for (int i = 1; i < n; i++) {
hold[i] = Math.max(hold[i - 1], rest[i - 1] - prices[i]);
sold[i] = hold[i - 1] + prices[i];
rest[i] = Math.max(rest[i - 1], sold[i - 1]);
}
return Math.max(sold[n - 1], rest[n - 1]);
}
}
💡 面试常见问题解答
Q1: 动态规划的核心思想是什么？
标准回答：
动态规划核心思想： 1. 最优子结构 - 问题的最优解包含子问题的最优解 - 可以通过子问题的最优解推导出原问题的最优解 2. 重叠子问题 - 递归过程中会重复计算相同的子问题 - 通过记忆化避免重复计算 3. 状态转移方程 - 描述状态之间的转换关系 - 是DP算法的核心 4. 解题步骤 - 定义状态 - 找出转移方程 - 确定边界条件 - 计算顺序 DP本质是用空间换时间的优化策略。
Q2: 背包问题的变种有哪些？
标准回答：
背包问题变种： 1. 0-1背包 - 每个物品只能选择一次 - 从右往左更新DP数组 2. 完全背包 - 每个物品可以选择无限次 - 从左往右更新DP数组 3. 多重背包 - 每个物品有数量限制 - 可以转化为0-1背包 4. 分组背包 - 物品分为若干组，每组只能选一个 - 三层循环：组、容量、物品 5. 应用问题 - 分割等和子集 - 目标和 - 零钱兑换 关键是理解状态转移的方向和含义。
Q3: 如何优化DP的空间复杂度？
标准回答：
DP空间优化策略： 1. 滚动数组 - 当前状态只依赖前几个状态 - 用一维数组代替二维数组 2. 状态压缩 - 用位运算表示状态 - 适用于状态数量较少的情况 3. 更新顺序 - 0-1背包：从右往左更新 - 完全背包：从左往右更新 - 避免状态被重复使用 4. 优化技巧 - 交换循环顺序 - 使用临时变量 - 原地更新 空间优化要保证状态转移的正确性。
核心要点总结：
- ✅ 掌握DP的基本思想和解题框架
- ✅ 熟练解决各种背包问题变种
- ✅ 理解最长子序列问题的状态设计
- ✅ 能够分析和优化DP的时间空间复杂度
Java面试圣经 文章被收录于专栏
Java面试圣经
投递影石Insta360等公司9个岗位