wordpress导航站的源码,wordpress comments,做网站最简单的方法,北京两区建设在哪里完全背包问题及背包问题总结 理论518. 零钱兑换 II322 零钱兑换279. 完全平方数139. 单词拆分#xff08;注意遍历顺序#xff09; 理论
1、完全背包即在0-1背包问题基础上#xff0c;一个物品可以选择多次 2、通用解决办法#xff1a;关键在递推过程
for i in range(len… 完全背包问题及背包问题总结 理论518. 零钱兑换 II322 零钱兑换279. 完全平方数139. 单词拆分注意遍历顺序 理论
1、完全背包即在0-1背包问题基础上一个物品可以选择多次 2、通用解决办法关键在递推过程
for i in range(len(weight)): # 遍历商品for j in range(bagWeight, weight[i]-1, -1): # 遍历背包容量 从大到小 0-1背包dp[j] max(dp[j], dp[j - weight[i]] value[i])for i in range(len(weight)): # 遍历商品for j in range(weight[i], bagWeight1): # 遍历背包容量 从小到大 完全背包dp[j] max(dp[j], dp[j - weight[i]] value[i])背包问题都是在此基础上的变形 递推公式 最多装多少dp[j] max(dp[j], dp[j - nums[i]] nums[i]); # nums[i]是价值 能否能装满
思路1最多装的等于包容量思路2True/Falsedp[j] dp[j] or dp[j - nums[i]]
几种方法dp[j] dp[j] dp[j - nums[i]] 装满背包所有物品的最小个数dp[j] min(dp[j], dp[j - nums[i]])
初始化一维数组一般只需要初始dp[0]
遍历顺序
0-1背包 二维dp数组01背包先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历 一维dp数组01背包只能先遍历物品再遍历背包容量且第二层for循环是从大到小遍历。如果先背包再物品由于从大到小遍历最后dp中保留是只放物品0的情况从大到小是为了防止对数据的覆盖根本原因是物品只能使用一次完全背包 如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。 注在一些题目中如果排列数和组合数不影响dp值则遍历顺序无所谓例322 零钱兑换
题目
面试要求写出代码分析初始化及遍历顺序 518. 零钱兑换 II
class Solution:def change(self, amount: int, coins: List[int]) - int:dp [0]*(amount1)# dp[j] 在coins[0]-[i]中选择硬币使其和为j的方法数# 初始化dp[0] 1# 递推for i in range(len(coins)):for j in range(coins[i], amount1):dp[j] dp[j] dp[j-coins[i]]return dp[-1]注遍历顺序不可调 先coins后amount得到的是组合数 先amount后coins得到的是排列数
遍历顺序问题参考
解释如果外层遍历的是coins若coins2则在计算dp[j]时只会用到当前即之前的硬币12不会用到之后的硬币 而如果外层遍历的是amount若amount3则在计算当前dp[j]如coins2时必然会使用到之前的dp而之前的dp是有coins2之后的硬币5参与的就是排列数的情况
322 零钱兑换
分析和上题类似只是求的是数量注意理解dp[j] 在递推公式的地方有点变化若加入当前硬币硬币数要1 dp初始化时要设为一个较大的数
class Solution:def coinChange(self, coins: List[int], amount: int) - int:dp [amount1]*(amount1) # 硬币数不可能为amount1 设较大值是由于递推公式求较小# dp[j] : 在0-i内硬币中取使金额为j的 最少硬币数目# 初始化dp[0] 0# 递推公式for i in range(len(coins)):for j in range(coins[i], amount1):dp[j] min(dp[j], dp[j-coins[i]]1) # 1是放入了coins[i]# 输出if dp[-1]amount1:return -1else:return dp[-1]# return dp[-1] if dp[-1] amount 1 else -1遍历顺序这题可以内外层次序调换不管是组合数还是排列数硬币数目不变
279. 完全平方数
分析 完全平方数就是商品可以反复使用——完全背包 要用商品凑满一个容量为n的包 求凑满所需的最少商品数 和上面的零钱兑换问题一致
class Solution:def numSquares(self, n: int) - int:# 计算商品 即为一个数的平方 且我们知道所需的商品最大不超过ngoods []for m in range(1,101):if m*mn:breakgoods.append(m*m)# dp[j] 装满大小为n的包需要的最少商品数dp [n1]*(n1) # 设为较大值由于递推取较小dp[0] 0# 递推for i in range(len(goods)):for j in range(goods[i], n1):dp[j] min(dp[j], dp[j-goods[i]]1) # 放入商品 商品数加1return dp[-1]改进无需知道商品具体值即无需算出平方后的量i**2是商品python的循环体特性导致无法实现c可以
遍历顺序由于问的是数量排列或组合对求和的数的数量无影响所以顺序可调换。
139. 单词拆分注意遍历顺序
分析 商品worddict中的所有字符串 可重复用——完全背包 背包字符串s 目标用商品组合成字符串 dp[j]: 以前i个字符串能否拼接出字符串s的前j个s[0:j1]) 注字符串i始终是末尾字符
递推公式TRUE OR FALSE或的关系
dp[j] dp[j] or (s[j-len(i):j]i and dp[j-len(i)])dp[j]不选字符串i 能否构成strs[j-len(i):j]i and dp[j-len(i)]选字符串i**前提是s末尾要同字符串i一致**class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:# 初始化dp [False]*(len(s)1)dp[0] True# 递推for j in range(len(s)1):for i in wordDict:if jlen(i):dp[j] dp[j] or (s[j-len(i):j]i and dp[j-len(i)])print(dp)return dp[-1]遍历顺序 以 “applepenapple” [“apple”,“pen”] 为例
选择字符串进行组合 2个apple和1个pen有3种 “pen”“apple”“apple”“apple”“pen”“apple”“apple”“apple”“pen” 很显然只有一种最后返回的是True即强调物品的顺序所以是排列而不是组合要先背包后遍历物品
参考听说背包问题很难 这篇总结篇来拯救你了
