查企业网站有哪些_电子商务专业怎么样_网络营销所学课程_下载手机百度最新版

322. 零钱兑换

leetcode 322. 零钱兑换
代码随想录

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:# dp[i] 表示凑成i所需要最小的硬币数量# 选了当前这个硬币coins[j]，之后剩下就是dp[i- coins[j]]# dp[i] = dp[i- coins[j]] + 1dp  = [float('inf')] * (amount + 1)dp[0] = 0for i in coins:for j in range(i,amount + 1):if dp[j-i] != float('inf'):dp[j] = min(dp[j], dp[j-i] + 1)return -1 if dp[-1] == float('inf') else dp[-1]

279.完全平方数

leetcode 279.完全平方数
代码随想录

class Solution:def numSquares(self, n: int) -> int:# dp[i]: 和为i的完全平方数的最小数量为dp[i]# dp[i] = dp[i - [完全平方数]] + 1dp = [n] * (n + 1)dp[0] = 0for i in range(1,int(n**0.5)+1):for j in range(i*i, n+1):dp[j] = min(dp[j], dp[j-i*i] + 1)return dp[-1]

139.单词拆分

leetcode 139.单词拆分
代码随想录

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:n = len(s)dp = [False] * (n+1)dp[0] = Truefor i in range(1,n+1):for j in wordDict:if i >= len(j):# 当前单词取出来，再看dp[i-len(j)]dp[i] = dp[i] or dp[i - len(j)] and j == s[i - len(j):i]return dp[-1]

多重背包

卡码网 56. 携带矿石资源
代码随想录 多重背包

多重背包把物品展开就变成了01背包。

C, N = map(int, input().split(" "))
weights = [int(x) for x in input().split(" ")]
values = [int(x) for x in input().split(" ")]
nums = [int(x) for x in input().split(" ")]dp = [0] * (C + 1)for i in range(N):for j in range(C, weights[i]-1,-1):for k in range(1, nums[i] + 1):if k * weights[i] > j:breakdp[j] = max(dp[j], dp[j- k*weights[i]] + k * values[i])
print(dp[-1])