Day 4：背包问题、最长递增子序列（LIS）

---

📖 一、动态规划（Dynamic Programming）简介

动态规划是一种通过将复杂问题分解成更小的子问题来解决问题的算法设计思想。它主要用于解决具有最优子结构和重叠子问题的问题。

• 最优子结构：问题的最优解可以通过子问题的最优解组合得到。
• 重叠子问题：子问题的解可以在多次计算中复用，避免了重复计算。

在使用动态规划时，通常会构造一个“状态转移方程”，该方程描述了如何通过子问题的解来得到当前问题的解。

---

📖 二、背包问题

01背包问题（0/1 Knapsack）

问题描述： 给定一个背包和若干个物品，每个物品有一个重量和价值。求背包能够承载的最大价值。

• 背包容量：W。
• 物品数目：n。
• 每个物品的重量和价值分别为 w[i] 和 v[i]。
• 我们需要选择一些物品放入背包，使得背包的总价值最大。

思路与分析：

1. 状态定义：
   • 定义 dp[i][w] 为前 i 个物品中，放入背包容量为 w 时能够达到的最大价值。
2. 状态转移：
   • 如果不选择第 i 个物品：dp[i][w] = dp[i-1][w]。
   • 如果选择第 i 个物品：dp[i][w] = dp[i-1][w - weight[i]] + value[i]，前提是 w >= weight[i]。
3. 最终的答案为 dp[n][W]。

代码实现（01背包问题）：

public class Knapsack {
    public int knapsack(int W, int[] weights, int[] values, int n) {
        // dp[i][w]表示前i个物品，背包容量为w时的最大价值
        int[][] dp = new int[n + 1][W + 1];
        
        // 填表，i表示物品数量，w表示背包容量
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                // 不选择第i个物品
                dp[i][w] = dp[i - 1][w];
                
                // 选择第i个物品，前提是背包容量足够
                if (w >= weights[i - 1]) {
                    dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        
        return dp[n][W];
    }

    public static void main(String[] args) {
        Knapsack knapsack = new Knapsack();
        int[] weights = {2, 3, 4, 5}; // 物品的重量
        int[] values = {3, 4, 5, 6};  // 物品的价值
        int W = 5;  // 背包容量
        int n = weights.length; // 物品数量
        
        int maxValue = knapsack.knapsack(W, weights, values, n);
        System.out.println("最大价值: " + maxValue); // 输出 7
    }
}

代码讲解：

1. 二维DP数组：dp[i][w] 表示前 i 个物品，背包容量为 w 时能达到的最大价值。
2. 状态转移：通过选择或不选择第 i 个物品来更新 dp[i][w]。
3. 时间复杂度：O(n * W)，其中 n 是物品的数量，W 是背包容量。

---

📖 三、最长递增子序列（LIS）

问题描述： 给定一个整数数组，求该数组的最长递增子序列（LIS）的长度。

• 数组的递增子序列是数组中的一个子序列，并且这个子序列中的元素是严格递增的。
• 我们要求的是最长递增子序列的长度。

思路与分析：

1. 状态定义：
   • 定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
2. 状态转移：
   • 对于每个元素 nums[i]，检查它之前的所有元素 nums[j]，如果 nums[i] > nums[j]，则更新 dp[i] 为 dp[j] + 1。
3. 最终的答案是 dp 数组中的最大值。

代码实现（LIS）：

public class LIS {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        int[] dp = new int[n];
        // 初始化dp数组，每个位置的初始值都是1
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

        // 枚举每个元素，检查之前的元素
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        // 找出dp数组的最大值，即最长递增子序列的长度
        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }
        
        return maxLength;
    }

    public static void main(String[] args) {
        LIS lis = new LIS();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("最长递增子序列的长度: " + lis.lengthOfLIS(nums)); // 输出 4
    }
}

代码讲解：

1. 动态规划数组：dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度。
2. 双重循环：对于每个元素 nums[i]，检查它之前的元素 nums[j]，如果满足递增条件，更新 dp[i]。
3. 最终结果：在 dp 数组中找出最大的值即为最长递增子序列的长度。

时间复杂度：

• O(n^2)，因为每个元素都需要与之前的所有元素比较。

---

📖 四、总结

背包问题常考点：

1. 01背包问题：经典的动态规划问题，重点是理解状态转移方程，通过选择与不选择物品来更新背包容量的最大价值。
2. 背包问题优化：可以使用滚动数组优化空间复杂度，将 dp 数组从二维优化为一维。

最长递增子序列（LIS）常考点：

1. 状态转移：LIS 是一个非常经典的动态规划问题。每个 dp[i] 由之前的所有 dp[j] 推导出。
2. 优化空间复杂度：O(n^2) 的时间复杂度较高，可以通过二分查找等优化方法将时间复杂度降到 O(n log n)。

常见易错点：

1. 背包问题：忘记更新 dp[i][w]，或者状态转移写反了，导致背包容量或物品数目错误。
2. LIS问题：对比 nums[i] > nums[j] 时，处理不当可能导致未能正确记录递增关系。