完全背包基础理论
https://programmercarl.com/背包问题理论基础完全背包.html#其他语言版本
卡码网完全背包例题
https://kamacoder.com/problempage.php?pid=1052
518.零钱兑换II
https://leetcode.cn/problems/coin-change-ii/description/
代码随想录
https://programmercarl.com/0518.零钱兑换II.html
377.组合总和 Ⅳ
https://leetcode.cn/problems/combination-sum-iv/
代码随想录
https://programmercarl.com/0377.组合总和Ⅳ.html#其他语言版本
70.爬楼梯（进阶版)
https://kamacoder.com/problempage.php?pid=1067
代码随想录
https://programmercarl.com/0070.爬楼梯完全背包版本.html#思路
完全背包基础理论
- 完全背包和01背包区别；
for循环正序遍历；
for j in range(weight[i],barweight)
def fullbag(n,v,weight,value):
dp = [0]*(v+1)
##初始化
for i in range(n):
for j in range(weight[i],v+1):##可以重复；所以从前往后即可
dp[j] = max(dp[j-weight[i]]+value[i],dp[j])
return dp[-1]
518.零钱兑换II
题解思路
- 完全背包解决组合问题
- dp[j]定义 和为j的最多可能组合
- 顺序必须是：先遍历物体 后遍历amount：是组合；
- 如果是 先遍历amount 后遍历物体：是排列；
题解代码
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0]*(amount+1)
dp[0] = 1 ##初始化金额0一定有一种解法
for coin in coins:
for j in range(coin,amount+1):
dp[j]+=dp[j-coin]
return dp[-1]
377. 组合总和 Ⅳ
题解思路
- 完全背包解决排列问题
-遍历顺序交换：先遍历数量 再遍历结果；
题解代码
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0]*(target+1)
dp[0] = 1 ##初始化金额0一定有一种解法
for j in range(0,target+1):
for num in nums:
if j>=num:
dp[j]+=dp[j-num]
return dp[-1]
70. 爬楼梯（进阶版）
题解思路
- 完全背包问题解决排列问题
题解代码
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0]*(amount+1)
dp[0] = 1 ##初始化金额0一定有一种解法
for coin in coins:
for j in range(coin,amount+1):
dp[j]+=dp[j-coin]
return dp[-1]