蓝桥杯 Java B 组之背包问题、最长递增子序列（LIS）

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

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

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

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

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

📖 二、背包问题

01背包问题（0/1 Knapsack）

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

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

思路与分析：

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

代码讲解：

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

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

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

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

思路与分析：

状态定义：
- 定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
状态转移：
- 对于每个元素 nums[i]，检查它之前的所有元素 nums[j]，如果 nums[i] > nums[j]，则更新 dp[i] 为 dp[j] + 1。
最终的答案是 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
    }
}