网站注册地查询昆明网站开发正规培训
https://leetcode-cn.com/problems/coin-change/solution/yi-tao-kuang-jia-jie-jue-bei-bao-wen-ti-h0y40/
背包问题具备的特征：
是否可以根据一个 target（直接给出或间接求出），target 可以是数字也可以是字符串，再给定一个数组 arrs，问：能否使用 arrs 中的元素做各种排列组合得到 target。
目录
一、01 背包问题
1.1 解法
二、完全背包
2.1 解法
三、01背包例题
416. 分割等和子集
494. 目标和
四、完全背包例题
139. 单词拆分
279. 完全平方数
322. 零钱兑换
518. 零钱兑换 II
一、01 背包问题
最基本的背包问题就是 01 背包问题：一共有 N 件物品，第 i（i 从 1 开始）件物品的重量为 w[i]，价值为 v[i]。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？
1.1 解法
如果是 01 背包，即数组中的元素不可重复使用，外循环遍历 arrs，内循环遍历 target，且内循环倒序:
二、完全背包
完全背包与 01 背包不同就是每种物品可以有无限多个：一共有 N 种物品，每种物品有无限多个，第 i（i 从 1 开始）种物品的重量为 w[i]，价值为 v[i]。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？
可见 01 背包问题与完全背包问题主要区别就是物品是否可以重复选取。
2.1 解法
（1）如果是完全背包，即数组中的元素可重复使用并且不考虑元素之间顺序，arrs 放在外循环（保证 arrs 按顺序），target 在内循环。且内循环正序。
（2）如果组合问题需考虑元素之间的顺序，需将 target 放在外循环，将 arrs 放在内循环，且内循环正序。
三、01背包例题
动态规划：0-1背包 理论回顾
for(int i=1; i<=m; i++) //物品 for(int j=t; j>=0; j--) //容量 {if(j >= w[i])dp[i][j] = max(dp[i-1][j-w[i]]+val[i], dp[i-1][j]);else //只是为了好理解，如果当前物体的容量>背包容量，就不装dp[i][j] = dp[i-1][j]; }空间优化
for(i=1;i<=m;i++){ //尝试放置每一个物品for(j=t;j>=w[i];j--){//倒叙是为了保证每个物品都使用一次f[j]=max(f[j-w[i]]+v[i],f[j]);//在放入第i个物品前后，检验不同j承重量背包的总价值，如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变}}416. 分割等和子集
494. 目标和
四、完全背包例题
377. 组合总和 Ⅳ
本质是考虑顺序的多重背包，target外层，arrs内层，内循环正序。
很好理解的动态规划问题，爬楼梯进化版
小明爬楼梯，每次可以爬的台阶数在nums中，要到达target阶，问有多少种走法？
本题的内核和上述场景一致。在 70. 爬楼梯 中常用的做法是 dp[n] = dp[n-1] + dp[n-2]。这里相当于nums = [1, 2]。含义是小明想要达到target阶，只有两种方法，第一种是从dp[n-1]出跨一步，第二种是从dp[n-2]出跨2步。
所以拓展到本题。小明想要达到target阶，
for i in range(target):for num in nums:# 只有这些可供选择的方法，在dp[i-num]处跨num步dp[i] += dp[i-num]
# 注意好边界的处理即可