代码随想录day46|139. 单词拆分

139. 单词拆分

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:dp = [False]*(len(s)+1)dp[0]=Truefor i in range(len(s)+1):for j in wordDict:if i>=len(j) and (s[i-len(j):i] in wordDict) and dp[i-len(j)]:dp[i] = Truereturn dp[len(s)]

多重背包即为每个物品有并不是只能用一次，也不是无限重复使用，而是有nums数组控制使用物品的个数，将其展开就变成了0-1背包问题

def test_multi_pack():weight = [1, 3, 4]value = [15, 20, 30]nums = [2, 3, 2]bagWeight = 10# 将数量大于1的物品展开for i in range(len(nums)):while nums[i] > 1:weight.append(weight[i])value.append(value[i])nums[i] -= 1dp = [0] * (bagWeight + 1)for i in range(len(weight)):  # 遍历物品for j in range(bagWeight, weight[i] - 1, -1):  # 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i])for j in range(bagWeight + 1):print(dp[j], end=" ")print()print(dp[bagWeight])test_multi_pack()

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

问装满背包有几种方法：dp[j] += dp[j - nums[i]]

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j])