面试重要程度：⭐⭐⭐⭐⭐

常见提问方式： "设计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
        // 因为要考虑不同顺序的