【代码随想录算法训练营第四十三天|卡码网52.携带研究材料、18.零钱兑换II、377.组合总和Ⅳ、卡码网57.爬楼梯】

卡码网52.携带研究材料

这题是完全背包问题，完全背包问题在01背包问题的基础上其实主要是三个不同，第一个是初始化的时候不能再和01背包一样对第一个物品让背包大小大于物品重量的时候全部初始化为物品价值，因为现在的物品可以无限放。第二个就是动态规划内部的循环推导的时候不用倒序而是正序了，因为之前提过正序会导致物品的重复使用，而现在正好是要重复使用。还有一个就是内外循环现在是可以交换的，只要保证dp前面的状态先于后面的状态计算出来就可以。

NV = input().split()
N, V = int(NV[0]), int(NV[1])
weights = []
values = []
for i in range(N):
    wv = input().split()
    weights.append(int(wv[0]))
    values.append(int(wv[1]))
dp = [0] * (V+1)
for i in range(N):
    for j in range(weights[i], V+1):
        dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
print(dp[-1])

518.零钱兑换II

就是一个完全背包问题，但是要注意只能外层硬币内层背包，不然会有重复的硬币组合。初始dp[0]要设置为1，相当于对dp[i-coin]当i为coin的时候设置为1。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1) 
        dp[0] = 1
        for coin in coins:
            for i in range(coin, amount+1):
                dp[i] += dp[i-coin]
        return dp[-1]

377.组合总和Ⅳ

其实这一题实际上要求的是排列，也就是上一题提到的背包在外的循环方式。

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(target+1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i-num]
        return dp[-1]

卡码网57.爬楼梯

和上面一题一样的，要求的是排列，所以楼层在外。

nm = input().split()
n, m = int(nm[0]), int(nm[1])
dp = [0] * (n+1)
dp[0] = 1
for i in range(1,n+1):
    for j in range(1,m+1):
        if i >= j:
            dp[i] += dp[i-j]
print(dp[-1])