完全背包问题总结
首先，需要清楚的是对于完全背包问题的定义：有N件物品和一个最多能背重量为 W 的背包。第 i 件物品的重量是 weight[i] ，得到的价值是 value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
相较于0/1背包问题，完全背包问题最大的不同之处在物品的个数是无限。那么在进行选择时，就是每一次向背包中添加物品时，都有 n 个物品可供选择（即从所有的物品中做任意的选择）。
完全背包问题的实现只需要在0/1背包的基础上稍作改动即可，依旧是采取滚动数组实现。
对于先便利物品，再遍历背包的情形：那么完全背包相较于0/1背包的不同之处，在第
i次迭代时，0/1背包只能使用一次物品weight[i]，因此采取从后向前的方式遍历，为了防止重复选择，但是完全背包可以使用任意次物品weight[i]，所以需要实现重复的选取，因此采取从前向后的遍历方式即可。并且这种先遍历物品再遍历背包的方式，本质上是在求解组合问题，也就是对于物品的选取顺序是不敏感的，仅对物品的个数敏感。（因为先遍历物品，因此也就确定了选取的顺序）先遍历背包，再遍历物品：也就是对于每一种情形下的背包容量，都从全部的物品中进行选择。在单纯的完全背包问题下，递推公式和结果是不会改变的。但是这样的遍历方式，本质上是在求解排列问题，也就是对于物品的选取顺序是敏感的，因为先遍历的是背包容量，在背包容量增大的过程中，最后一次选取的物品不同将会是不同的情形。
LeetCode 377 组合总和Ⅳ
给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
本题求解的并不是组合问题，是一个排序问题，在题目示例中将 1,2,1 和 1,1,2 视为两种不同的组合，也就是对于元素的选取顺序是敏感的。那么应该先遍历背包再遍历物品，并且此处求解的是恰好装满的情形，相应的递推公式为 dp[j]+=dp[j-nums[i]]
LeetCode 518 零钱兑换II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
根据题中的示例，本题求解的是一个组合问题。
并且此处的背包问题是一个恰好装满的情形，那么对于组合问题基本思路就是先遍历物品再遍历背包，那么递推公式为： dp[j]+=dp[j-coins[i]] ，在进行初始化是一定要将 dp[0]=1
LeetCode 322 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
此处的最优化问题为：求解能够恰好装满背包的最少硬币数量，那么对于组合和排列都是相同的，两种遍历顺序都是可以的。基本的递推公式为：dp[j]=min(dp[j],dp[j-coins[i]]+1) ，要让上述递推公式成立，需要在数组的初始化时进行特殊处理，对于 dp[0] 只需要0个硬币即可装满。那么对于其他的值明显都装不满，因此初始为 INT_MAX ，并且每次判断 dp[j-coins[i]]!=INT_MAX
LeetCode 279 完全平方数
给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。
完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
此处和上述问题是非常类似的，也是在求解将背包恰好装满的最少的元素数量。但是此处的元素要求是完全平方数，因此在遍历物品的同时去生成相应的完全平方数即可。对于 dp[0] 依旧是初始化为0。其他元素全部初始化为 INT_MAX 。对应的递推公式为 dp[j]=min(dp[j],dp[j-nums[i]]+1) 要求 dp[j-nums[i]]!=INT_MAX
LeetCode 139 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
此处需要注意的是：本题是一个排列问题，一定要先遍历背包，再遍历物品，也就是对于任意的背包大小都要能够使用全部的物品去进行填充，否则对于 applepenapple 这样的情形，在仅使用 apple 时，不能将后续的也标记为装满。那么在使用 pen 去填充时，无法使用 apple 将后续填满。