动态规划经典问题解析

一、0/1背包问题

1.1 问题

n个物品，重量w[i]，价值v[i]，背包容量W，求最大价值。

1.2 状态定义

dp[i][j] = 考虑前i个物品，容量为j时的最大价值

1.3 状态转移

不选第i个：dp[i][j] = dp[i-1][j]
选第i个：dp[i][j] = dp[i-1][j-w[i]] + v[i]
dp[i][j] = max(不选, 选)

public int knapsack(int[] w, int[] v, int W) {
    int n = w.length;
    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];
}

1.4 空间优化

public int knapsackOptimized(int[] w, int[] v, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < w.length; i++) {
        for (int j = W; j >= w[i]; j--) {  // 倒序！
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

倒序遍历防止物品被重复选取。

二、完全背包

2.1 问题

每个物品可以选无限次。

2.2 状态转移

// 正序遍历
for (int j = w[i]; j <= W; j++) {
    dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}

2.3 与0/1背包的区别

• 0/1背包：倒序（每个物品只能用一次）
• 完全背包：正序（可以重复使用）

三、编辑距离

3.1 问题

将word1转换为word2的最少操作数（插入、删除、替换）。

3.2 状态

dp[i][j] = word1[0..i) 转 word2[0..j) 的最小操作数

3.3 实现

public 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] = Math.min(
                    dp[i - 1][j] + 1,      // 删除
                    Math.min(
                        dp[i][j - 1] + 1,  // 插入
                        dp[i - 1][j - 1] + 1  // 替换
                    )
                );
            }
        }
    }
    return dp[m][n];
}

四、股票买卖问题

4.1 买卖一次

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;
    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }
    return maxProfit;
}

4.2 买卖多次

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

4.3 含冷冻期

public int maxProfitWithCooldown(int[] prices) {
    int n = prices.length;
    if (n < 2) return 0;
    
    // hold: 持有股票, sold: 刚卖出, rest: 不持有
    int hold = -prices[0], sold = 0, rest = 0;
    
    for (int i = 1; i < n; i++) {
        int prevSold = sold;
        sold = hold + prices[i];
        hold = Math.max(hold, rest - prices[i]);
        rest = Math.max(rest, prevSold);
    }
    return Math.max(sold, rest);
}

五、总结

问题类型	状态设计	关键点
0/1背包	dp[j]容量j的最大价值	倒序遍历
完全背包	dp[j]容量j的最大价值	正序遍历
编辑距离	dp[i][j]子串转换代价	三种操作
股票问题	每天的状态机转移	定义清楚每天的状态

动态规划的难点在于状态设计。多练习经典问题，总结状态设计的模式，是掌握DP的关键。