网站域名重定向,上海市住房和城乡建设部网站官网,网站开发哪家好,成都景点Day 4#xff1a;背包问题、最长递增子序列#xff08;LIS#xff09; #x1f4d6; 一、动态规划#xff08;Dynamic Programming#xff09;简介
动态规划是一种通过将复杂问题分解成更小的子问题来解决问题的算法设计思想。它主要用于解决具有最优子结构和重叠子问题…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数组每个位置的初始值都是1for (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}
}代码讲解
动态规划数组dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度。双重循环对于每个元素 nums[i]检查它之前的元素 nums[j]如果满足递增条件更新 dp[i]。最终结果在 dp 数组中找出最大的值即为最长递增子序列的长度。
时间复杂度
O(n^2)因为每个元素都需要与之前的所有元素比较。 四、总结
背包问题常考点
01背包问题经典的动态规划问题重点是理解状态转移方程通过选择与不选择物品来更新背包容量的最大价值。背包问题优化可以使用滚动数组优化空间复杂度将 dp 数组从二维优化为一维。
最长递增子序列LIS常考点
状态转移LIS 是一个非常经典的动态规划问题。每个 dp[i] 由之前的所有 dp[j] 推导出。优化空间复杂度O(n^2) 的时间复杂度较高可以通过二分查找等优化方法将时间复杂度降到 O(n log n)。
常见易错点
背包问题忘记更新 dp[i][w]或者状态转移写反了导致背包容量或物品数目错误。LIS问题对比 nums[i] nums[j] 时处理不当可能导致未能正确记录递增关系。
