100. Leetcode 377. 组合总和 Ⅳ (动态规划-完全背包)

根据题意可判断属于完全背包队列问题

步骤一、确定状态:

确定dp数组及下标含义

dp数组的大小是target+1, 那么这时候背包的容量才能取到target， dp[j]表示的是装满容量为[j]的背包有多少种方法

步骤二、推断状态方程:

这个和上面的零钱兑换II的一样 dp[j] += dp[j-nums[i]]

步骤三、规定初始条件:

初始条件:

全局初始化为0， 而dp[0] = 1

步骤四、计算顺序:

对于物品， 依然是正向遍历，而对于背包，也是正向遍历，因为这里的物品 可以取多次

class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:if len(nums) == 0 or target == 0:return 0# dp[i]: 容量为i的背包有多少种装法 dp = [0 for _ in range(target+1)]dp[0] = 1 # 初始化for j in range(target + 1): # 遍历背包容量for i in range(len(nums)): # 遍历物品if j >= nums[i]:dp[j] += dp[j - nums[i]]return dp[-1]

总结

以上是生活随笔为你收集整理的100. Leetcode 377. 组合总和 Ⅳ (动态规划-完全背包)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。