2017网站建设报价单免费网站空间怎么

2017网站建设报价单,免费网站空间怎么,静态做头像的网站,公司网站维护一般需要做什么目录 一、背包问题核心理论 1. 背包问题定义 2. 通用解题框架 3. 遍历顺序底层逻辑 二、01 背包典型题目#xff1a; #xff08;一#xff09;目标和#xff08;LeetCode 494#xff09; 1. 题目描述 2. 问题转化#xff08;核心#xff01;#xff09; 3. 详…目录一、背包问题核心理论1. 背包问题定义2. 通用解题框架3. 遍历顺序底层逻辑二、01 背包典型题目一目标和LeetCode 4941. 题目描述2. 问题转化核心3. 详细分析状态定义初始化状态转移4. 易错点踩过的坑5. 难点6. Java 实现二维 DP 解法---好理解一点新手友好一维 DP 解法空间优化7. 过程展示二维 DP 表填充关键行一维 DP 更新过程二分割等和子集LeetCode 4161、题目描述2、问题转化01 背包核心2.1 核心推导2.2 对应背包模型3、详细分析3.1 状态定义3.2 初始化基准状态3.3 状态转移二维转移一维转移倒序01 背包核心4、易错点高频踩坑5、难点6、Java 实现1. 二维 DP 解法易理解新手首选2. 一维 DP 解法空间优化刷题常用7、过程展示示例 1nums[1,5,11,5]s22target117.1 二维 DP 表填充关键行7.2 一维 DP 更新过程8、与 “目标和” 的对比01 背包两类目标三、完全背包典型题目一最少硬币数LeetCode 3221. 题目描述2. 问题转化3. 详细分析状态定义初始化状态转移4. 易错点5. 难点6. Java 实现二维 DP 解法一维 DP 解法7. 过程展示二完全平方数的最少数量LeetCode 2791. 题目描述2. 问题转化3. 详细分析状态定义初始化状态转移4. 易错点5. 难点6. Java 实现二维 DP 解法一维 DP 解法7. 过程展示三单词拆分LeetCode 1391. 题目描述2. 问题转化3. 详细分析状态定义初始化状态转移4. 易错点5. 难点6. Java 实现二维 DP 解法一维 DP 解法优化7. 过程展示四、整体总结1. 01 背包 vs 完全背包核心对比2. 解题通用步骤背下来3. 关键思维一、背包问题核心理论1. 背包问题定义背包问题是动态规划的经典分支核心是「给定物品集合 目标容量通过选择物品满足容量约束求最优解数量 / 最值 / 布尔值」主要分为两类背包类型核心规则适用场景核心遍历逻辑01 背包每个物品只能选 1 次目标和、分割等和子集先物品 → 倒序遍历容量防重复完全背包每个物品可重复选最少硬币数、完全平方数先物品 → 正序遍历容量允重复2. 通用解题框架无论 01 / 完全背包核心步骤一致仅在「遍历顺序 / 转移细节」有差异问题转化识别「物品」「容量」「优化目标」方案数 / 最值 / 布尔值状态定义dp[i][j]二维 考虑前i个物品容量为j的最优解dp[j]一维 容量为j的最优解空间优化初始化确定基准状态如dp[0][0]1/dp[0]0状态转移基于「选 / 不选当前物品」推导遍历顺序按背包类型确定01 倒序 / 完全正序。3. 遍历顺序底层逻辑01 背包倒序避免同一物品被重复选更新大索引时小索引仍为「上一轮状态」完全背包正序允许同一物品被重复选更新大索引时小索引已为「本轮状态」完全背包可互换「物品 / 容量」遍历顺序01 背包不可必须先物品后倒序容量。二、01 背包典型题目一目标和LeetCode 4941. 题目描述给定整数数组nums和目标值target给每个数加或-求最终和为target的方案数。示例nums[1,1,1,1,1], target3→ 输出 5。2. 问题转化核心设数组总和为s选部分数加和为p另一部分加-和为s-pp - (s-p) target→ 化简得p (target s) / 2。问题转化为从nums中选若干数每个数只能选 1 次和为p的方案数01 背包。3. 详细分析状态定义二维dp[i][j] 考虑前i个数凑和为j的方案数一维dp[j] 凑和为j的方案数空间优化。初始化二维dp[0][0] 1无物品时凑 0 的方案数 1dp[0][j0] 0一维dp[0] 1基准其余默认 0。状态转移二维if (j nums[i-1]) { // 选dp[i-1][j-nums[i-1]] 不选dp[i-1][j] dp[i][j] dp[i-1][j] dp[i-1][j - nums[i-1]]; } else { dp[i][j] dp[i-1][j]; // 不够选只能不选 }一维倒序for (int num : nums) { for (int j p; j num; j--) { dp[j] dp[j - num]; // 选不选的叠加 } }4. 易错点踩过的坑变量名混淆用target存总和导致逻辑混乱需单独用s存总和p存目标和遍历顺序错误正序遍历容量→变成完全背包重复选数合法性判断缺失未判断(targets)是否为偶数、p是否非负初始化遗漏未设dp[0]1基准丢失结果全 0。5. 难点问题转化从「加减符号」抽象出「01 背包」的思维跳跃一维遍历逻辑倒序的底层原因避免重复选数边界处理p为负 / 总和小于|target|的特殊情况。6. Java 实现二维 DP 解法---好理解一点新手友好class Solution { public int findTargetSumWays(int[] nums, int target) { // 1. 计算总和合法性判断 int s 0; for (int num : nums) s num; if (Math.abs(target) s || (target s) % 2 ! 0) return 0; int p (target s) / 2; if (p 0) return 0; // 2. 二维DP初始化 int n nums.length; int[][] dp new int[n 1][p 1]; dp[0][0] 1; // 基准 // 3. 状态转移 for (int i 1; i n; i) { int num nums[i - 1]; for (int j 0; j p; j) { if (j num) { dp[i][j] dp[i-1][j] dp[i-1][j - num]; } else { dp[i][j] dp[i-1][j]; } } } return dp[n][p]; } }一维 DP 解法空间优化class Solution { public int findTargetSumWays(int[] nums, int target) { int s 0; for (int num : nums) s num; if (Math.abs(target) s || (target s) % 2 ! 0) return 0; int p (target s) / 2; if (p 0) return 0; int[] dp new int[p 1]; dp[0] 1; // 基准 // 01背包先物品后倒序容量 for (int num : nums) { for (int j p; j num; j--) { dp[j] dp[j - num]; } } return dp[p]; } }7. 过程展示以nums[1,1,1,1,1], target3s5, p4为例二维 DP 表填充关键行i\j0123401000011100021210031331041464151510105最终dp[5][4]5正确答案。一维 DP 更新过程初始dp[1,0,0,0,0]遍历第 1 个 1dp[1,1,0,0,0]遍历第 2 个 1dp[1,2,1,0,0]遍历第 3 个 1dp[1,3,3,1,0]遍历第 4 个 1dp[1,4,6,4,1]遍历第 5 个 1dp[1,5,10,10,5]。二分割等和子集LeetCode 416这道题是 01 背包的基础布尔型应用目标是 “能否凑满容量”比 “目标和” 更贴近 01 背包的原始模型是理解 “01 背包判断可行性” 的关键题目补充后能完整覆盖 01 背包的 “方案数” 和 “可行性” 两类目标。1、题目描述给定一个只包含正整数的非空数组nums判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。示例 1输入nums[1,5,11,5]→ 输出true子集 1[1,5,5]子集 2[11]和均为 11示例 2输入nums[1,2,3,5]→ 输出false总和 11 为奇数无法分割。2、问题转化01 背包核心2.1 核心推导要分割成两个和相等的子集 → 数组总和s必须是偶数否则直接返回false设目标和target s / 2→ 问题转化为从nums中选若干数每个数只能选 1 次能否凑出和为target01 背包的 “可行性判断”。2.2 对应背包模型物品数组中的每个数字每个只能选 1 次容量target总和的一半目标判断 “能否用物品装满容量”布尔值。3、详细分析3.1 状态定义二维 DPdp[i][j] 考虑前i个数字能否凑出和为jtrue/falsei前i个数字范围 0~nums.lengthi0表示无数字j目标和范围 0~target。一维 DPdp[j] 能否凑出和为j空间优化压缩i维度。3.2 初始化基准状态二维dp[0][0] true无数字时凑出和为 0 的方案存在选 0 个数dp[0][j0] false无数字时无法凑出大于 0 的和。一维dp[0] true基准其余默认falseJava 布尔数组默认值。3.3 状态转移核心逻辑对第i个数字对应nums[i-1]分 “选” 和 “不选” 两种情况二维转移if (j nums[i-1]) { // 选dp[i-1][j-nums[i-1]]前i-1个数凑j-nums[i-1]可行 OR 不选dp[i-1][j] dp[i][j] dp[i-1][j] || dp[i-1][j - nums[i-1]]; } else { // 数字比j大无法选继承“不选”的结果 dp[i][j] dp[i-1][j]; }一维转移倒序01 背包核心for (int num : nums) { // 倒序遍历避免同一数字被重复选 for (int j target; j num; j--) { // 只要“不选num可行”或“选num可行”dp[j]就为true dp[j] dp[j] || dp[j - num]; } }4、易错点高频踩坑总和奇偶性判断缺失直接开始 DP忽略s为奇数的情况必返回false遍历顺序错误正序遍历容量→变成完全背包数字被重复选比如nums[2,2]正序会错误返回true但实际 01 背包也正确需注意布尔型 01 背包正序可能结果对但逻辑错元素剪枝遗漏数组中存在num target的元素直接返回false因为单个元素超过目标和无法凑出初始化错误未设dp[0]true基准丢失所有状态都为false。5、难点问题抽象能力从 “分割子集” 到 “01 背包可行性” 的转化新手易卡在这一步提前剪枝优化总和为奇数 → 直接返回false单个元素 target → 直接返回false遍历中若dp[target]提前变为true可直接返回剪枝一维遍历的逻辑理解倒序的本质是 “保证每个数字只选一次”和目标和的一维逻辑完全一致。6、Java 实现1. 二维 DP 解法易理解新手首选class Solution { public boolean canPartition(int[] nums) { // 1. 计算总和合法性判断 int s 0; for (int num : nums) s num; // 总和为奇数直接返回false if (s % 2 ! 0) return false; int target s / 2; // 2. 二维DP初始化 int n nums.length; boolean[][] dp new boolean[n 1][target 1]; dp[0][0] true; // 基准无数字凑0可行 // 3. 状态转移 for (int i 1; i n; i) { int num nums[i - 1]; // 剪枝当前数字超过target直接继承上一行结果 if (num target) return false; for (int j 0; j target; j) { if (j num) { dp[i][j] dp[i-1][j] || dp[i-1][j - num]; } else { dp[i][j] dp[i-1][j]; } } // 提前剪枝已找到可行方案 if (dp[i][target]) return true; } return dp[n][target]; } }2. 一维 DP 解法空间优化刷题常用class Solution { public boolean canPartition(int[] nums) { int s 0; for (int num : nums) s num; if (s % 2 ! 0) return false; int target s / 2; // 一维DP初始化dp[0]true其余false boolean[] dp new boolean[target 1]; dp[0] true; // 01背包先物品后倒序容量 for (int num : nums) { // 剪枝当前数字超过target无法凑出 if (num target) return false; for (int j target; j num; j--) { dp[j] dp[j] || dp[j - num]; } // 提前剪枝 if (dp[target]) return true; } return dp[target]; } }7、过程展示示例 1nums[1,5,11,5]s22target117.1 二维 DP 表填充关键行i\j012345678910110TFFFFFFFFFFF1num1TTFFFFFFFFFF2num5TTFFFTTFFFFF3num11TTFFFTTFFFFT4num5TTFFFTTFFFTT✅ 遍历到i3num11时dp[3][11]true提前返回true。7.2 一维 DP 更新过程初始dp[T,F,F,F,F,F,F,F,F,F,F,F]索引 0~11遍历 num1dp[T,T,F,F,F,F,F,F,F,F,F,F]遍历 num5dp[T,T,F,F,F,T,T,F,F,F,F,F]遍历 num11dp[T,T,F,F,F,T,T,F,F,F,F,T]dp [11]true提前返回。8、与 “目标和” 的对比01 背包两类目标题目01 背包目标状态转移核心初始化基准分割等和子集可行性布尔值dp[j] dp[j]dp[j-num]dp[0]true目标和方案数数值dp[j] dp[j-num]dp[0]1共性均需倒序遍历容量依赖 “选 / 不选” 的状态叠加以dp[0]为基准三、完全背包典型题目一最少硬币数LeetCode 3221. 题目描述给定硬币数组coins可重复用和金额amount求凑成amount的最少硬币数凑不出返回 - 1。示例coins[1,2,5], amount11→ 输出 3551。2. 问题转化物品 硬币容量 金额每个物品可重复选求「凑满容量的最少物品数」完全背包求 min。3. 详细分析状态定义二维dp[i][j] 考虑前i种硬币凑金额j的最少硬币数一维dp[j] 凑金额j的最少硬币数。初始化二维dp[0][0] 0dp[0][j0] amount1标记 “不可达”一维dp[0] 0其余初始为amount1避免用Integer.MAX_VALUE溢出。状态转移二维if (j coins[i-1]) { // 选dp[i][j-coins[i-1]]1可重复选用dp[i]而非dp[i-1] dp[i][j] Math.min(dp[i-1][j], dp[i][j - coins[i-1]] 1); } else { dp[i][j] dp[i-1][j]; }一维正序for (int coin : coins) { for (int j coin; j amount; j) { dp[j] Math.min(dp[j], dp[j - coin] 1); } }4. 易错点初始化错误用i1而非amount1小金额初始值不合理剪枝依赖缺失break需先排序硬币否则漏解结果判断缺失未检查dp[amount]是否仍为amount1需返回 - 1。5. 难点不可达标记选择amount1是最优避免溢出完全背包的 “重复选” 逻辑二维用dp[i]而非dp[i-1]排序 剪枝的优化逻辑硬币大于金额时跳过。6. Java 实现二维 DP 解法class Solution { public int coinChange(int[] coins, int amount) { int n coins.length; int[][] dp new int[n 1][amount 1]; // 初始化不可达标记为amount1 for (int j 1; j amount; j) { dp[0][j] amount 1; } dp[0][0] 0; for (int i 1; i n; i) { int coin coins[i-1]; for (int j 0; j amount; j) { if (j coin) { dp[i][j] Math.min(dp[i-1][j], dp[i][j - coin] 1); } else { dp[i][j] dp[i-1][j]; } } } return dp[n][amount] amount 1 ? -1 : dp[n][amount]; } }一维 DP 解法class Solution { public int coinChange(int[] coins, int amount) { int[] dp new int[amount 1]; Arrays.fill(dp, amount 1); dp[0] 0; // 完全背包先物品后正序容量 for (int coin : coins) { for (int j coin; j amount; j) { dp[j] Math.min(dp[j], dp[j - coin] 1); } } return dp[amount] amount 1 ? -1 : dp[amount]; } }7. 过程展示以coins[1,2,5], amount11为例一维初始dp[0,12,12,12,12,12,12,12,12,12,12,12]遍历 coin1dp[0,1,2,3,4,5,6,7,8,9,10,11]遍历 coin2dp[0,1,1,2,2,3,3,4,4,5,5,6]遍历 coin5dp[0,1,1,2,2,1,2,2,3,3,2,3]最终dp[11]3正确。二完全平方数的最少数量LeetCode 2791. 题目描述给定整数n求组成n的最少完全平方数数量。示例n12→ 输出 3444。2. 问题转化物品 完全平方数1,4,9,...容量 n物品可重复选求「凑满容量的最少物品数」完全背包求 min。3. 详细分析状态定义二维dp[i][j] 考虑前i个平方数凑j的最少数量一维dp[j] 凑j的最少数量。初始化二维dp[0][0]0dp[0][j0]j最坏全用 1一维dp[0]0其余初始为j。状态转移二维int square i * i; // 第i个平方数为i² if (j square) { dp[i][j] Math.min(dp[i-1][j], dp[i][j - square] 1); } else { dp[i][j] dp[i-1][j]; }一维正序for (int i 1; i * i n; i) { int square i * i; for (int j square; j n; j) { dp[j] Math.min(dp[j], dp[j - square] 1); } }4. 易错点贪心陷阱优先选最大平方数如 n12 贪心得 4实际 3平方数遍历边界未限制i*i n导致越界状态转移遗漏未取 min直接覆盖值。5. 难点贪心 vsDP 的取舍局部最优≠全局最优数学定理优化拉格朗日四平方和定理O (√n) 时间平方数的生成逻辑避免重复计算。6. Java 实现二维 DP 解法class Solution { public int numSquares(int n) { int maxSquare (int) Math.sqrt(n); int[][] dp new int[maxSquare 1][n 1]; // 初始化 for (int j 1; j n; j) { dp[0][j] j; } dp[0][0] 0; for (int i 1; i maxSquare; i) { int square i * i; for (int j 0; j n; j) { if (j square) { dp[i][j] Math.min(dp[i-1][j], dp[i][j - square] 1); } else { dp[i][j] dp[i-1][j]; } } } return dp[maxSquare][n]; } }一维 DP 解法class Solution { public int numSquares(int n) { int[] dp new int[n 1]; for (int j 1; j n; j) { dp[j] j; // 初始化最坏情况 } dp[0] 0; for (int i 1; i * i n; i) { int square i * i; for (int j square; j n; j) { dp[j] Math.min(dp[j], dp[j - square] 1); } } return dp[n]; } }7. 过程展示以n12为例一维初始dp[0,1,2,3,4,5,6,7,8,9,10,11,12]遍历 square1无变化已最优遍历 square4dp[4]1, dp[8]2, dp[12]3遍历 square9dp[9]1, dp[12]min(3, dp[3]14) → 3最终dp[12]3正确。三单词拆分LeetCode 1391. 题目描述给定字符串s和单词列表wordDict判断s能否拆分为字典中的单词单词可重复用。示例sleetcode, wordDict[leet,code]→ 输出 true。2. 问题转化物品 字典单词容量 字符串长度物品可重复选求「能否用单词拼接出前i个字符」完全背包求布尔值。3. 详细分析状态定义二维dp[i][j] 考虑前i个单词能否拼接出s的前j个字符一维dp[j] 能否拼接出s的前j个字符。初始化二维dp[0][0] true无单词时空串可拼接一维dp[0] true基准其余为 false。状态转移二维String word wordDict.get(i-1); int len word.length(); if (j len s.substring(j-len, j).equals(word)) { dp[i][j] dp[i-1][j] || dp[i][j - len]; } else { dp[i][j] dp[i-1][j]; }一维正序for (int j 1; j s.length(); j) { for (String word : wordDict) { int len word.length(); if (j len dp[j - len] s.substring(j-len, j).equals(word)) { dp[j] true; break; } } }4. 易错点贪心陷阱用 flag 锁定拆分位置错过正确路径索引错误substring的左闭右开规则如j-len到j初始化错误未设dp[0]true基准丢失查询效率低未用HashSet优化字典查询。5. 难点字符串与背包的转化将 “拼接” 抽象为 “凑容量”子串截取的边界处理避免越界布尔值的状态转移只要有一条路径可行即为 true。6. Java 实现二维 DP 解法class Solution { public boolean wordBreak(String s, ListString wordDict) { int n wordDict.size(); int m s.length(); boolean[][] dp new boolean[n 1][m 1]; dp[0][0] true; // 基准 for (int i 1; i n; i) { String word wordDict.get(i-1); int len word.length(); for (int j 0; j m; j) { dp[i][j] dp[i-1][j]; // 先继承不选当前单词的结果 if (j len s.substring(j-len, j).equals(word)) { dp[i][j] dp[i][j] || dp[i][j - len]; } } } return dp[n][m]; } }一维 DP 解法优化class Solution { public boolean wordBreak(String s, ListString wordDict) { int m s.length(); boolean[] dp new boolean[m 1]; dp[0] true; SetString wordSet new HashSet(wordDict); // 优化查询 // 完全背包先容量后物品等价 for (int j 1; j m; j) { for (String word : wordSet) { int len word.length(); if (j len dp[j - len] s.substring(j-len, j).equals(word)) { dp[j] true; break; } } } return dp[m]; } }7. 过程展示以sleetcode, wordDict[leet,code]为例一维初始dp[true,false,false,false,false,false,false,false,false]j4substring(0,4)leetdp[0]true→dp[4]truej8substring(4,8)codedp[4]true→dp[8]true最终dp[8]true正确。四、整体总结1. 01 背包 vs 完全背包核心对比维度01 背包完全背包选取规则物品选 1 次物品可重复选遍历顺序先物品→倒序容量先物品→正序容量可互换二维转移依赖dp[i-1][j-num]依赖dp[i][j-num]核心应用目标和、分割等和子集最少硬币数、完全平方数易错点正序遍历导致重复选贪心陷阱、初始化溢出2. 解题通用步骤背下来识别背包类型判断物品能否重复选01 / 完全抽象物品 容量01 背包物品 数字容量 目标和完全背包物品 硬币 / 平方数 / 单词容量 金额 / 数值 / 字符串长度定义状态二维易理解→ 一维空间优化初始化基准方案数dp[0]1最值dp[0]0其余为极大 / 极小值布尔值dp[0]true其余为 false状态转移基于「选 / 不选」推导取 min/max/ 叠加 / 或遍历顺序按背包类型确定验证边界。3. 关键思维DP 的核心是「覆盖所有路径」而非贪心的「局部最优」二维 DP 是理解本质的基础一维 DP 是刷题的最优选择背包问题的本质是「状态的复用」遍历顺序决定复用规则。