主要总结了完全背包问题
对应leetcode题目为518.377.279.70.139
代码地址https://github.com/Ltd5552/Algorithm/tree/master/8-DP/Bag
理论
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
之前01背包提到了必须倒序遍历，否则会导致同一物品被多次加入，完全背包问题正好就可以多次加入同一物品，所以只需要在01背包的基础上更改遍历顺序为顺序遍历即可。
同时，由于递推方向是从左往右，物品可以多次放进去，所以不论先遍历物品还是先遍历背包都可以，因为即使先遍历背包也能够保证之前的计算过了，不会出现只有一个物品的情况。
// ComBagSolutionI 先遍历物品再遍历背包
func ComBagSolutionI(weight, value []int, bagWeight int) int {
dp := make([]int, bagWeight+1)
for i := range weight {
//正向遍历，可以重复装入某一个物品
for j := weight[i]; j <= bagWeight; j++ {
//一维dp是靠前面的推导出来的
dp[j] = utils.Max(dp[j], dp[j-weight[i]]+value[i])
}
}
return dp[bagWeight]
}
// ComBagSolutionII 先遍历背包容量再遍历物品
func ComBagSolutionII(weight, value []int, bagWeight int) int {
dp := make([]int, bagWeight+1)
for j := 0; j <= bagWeight; j++ {
//正向遍历，可以重复装入某一个物品
for i := range weight {
if j >= weight[i] {
//一维dp是靠前面的推导出来的
dp[j] = utils.Max(dp[j], dp[j-weight[i]]+value[i])
}
}
}
return dp[bagWeight]
}
518.零钱兑换II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10]
输出：1
分析
与开篇的纯完全背包问题不同，纯完全背包是求装包的最大价值，而这里是装满的物品组合个数，和之前的目标和差不多。
组合不强调元素之间的顺序，排列强调元素之间的顺序。
动规：
-
定义dp[j]为凑成金额j的货币组合个数；
-
dp[j]就是全部dp[j-coins[i]]情况相加，所以递推公式就是
dp[j] += dp[j-coins[i]]，这里也和目标和一样； -
如何初始化？还是dp[0] = 1，这是后面所有的基础，如果为0的话全都为0了，其他的默认0即可，这样才不会影响正确的结果，本身开始也没啥意义。
-
遍历顺序
完全背包问题的遍历顺序依旧非常关键，对于纯完全背包问题而言因为是求最大价值，不管怎么排列组合都行，结果没影响；但这里是求装满的方案数，这里的方案数明确要求是顺序无关的，即组合数。
如果先遍历背包再遍历物品，那么对背包容量的每一个值都会经过全部物品，这样针对的是前面的所有可能的取值，比如计算i=4的时候，假设存在{1, 3}那么就会包含
dp[4] += dp[4-1]和dp[4]+=dp[4-3]两种排列（但只是一种组合），这样结果就是排列数；如果先遍历物品再遍历背包，那么对于每一个物品的遍历只会“占据一行”，这一次遍历完了后面就不会再出现了，所以上面的例子也只会出现
dp[4] += dp[4-1]的情况（1在5前面），而不会说遍历完5了又来遍历一次1，他们的相对顺序一定是绝对的（1在5前面就在5前面，不会跑到5后面去，这样自然就不会出现{5, 1}的情况了），这样结果就是组合数。func change(amount int, coins []int) int { dp := make([]int, amount+1) dp[0] = 1 for i := range coins { for j := coins[i]; j <= amount; j++ { dp[j] += dp[j-coins[i]] } } return dp[amount] }对比的代码在这里可以查看
377.组合总和IV
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
分析
经过上一题的分析这道题显然就是求排列数了，目标target即背包容量，nums即元素的数组，价值和重量同样都是对应的数值。
具体区别就只有遍历顺序不同。
func combinationSum4(nums []int, target int) int {
dp := make([]int, target+1)
dp[0] = 1
for i := 1; i <= target; i++ {
for j := range nums {
if i >= nums[j] {
dp[i] += dp[i-nums[j]]
}
}
}
return dp[target]
}
279.完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
动规
求和为n的完全平方数最小个数，那么就是背包容量为n，物品是1/4/9/16…的完全背包问题了。
定义dp[i]为当容量为i时满足装满条件下完全平方数的最少个数，递推式dp[i] = min(dp[i], dp[i-nums[j]]+1)
这里的初始化值得注意，因为是求最少个数，那么就得初始化为一个较大的值在后续才能去更小的，所以这里初始化为math.MaxInt
求最小数，与排列组合没有关系，所以先遍历物品或先遍历背包都可以。
func numSquares(n int) int {
dp := make([]int, n+1)
for i := 1; i <= n; i++ {
dp[i] = math.MaxInt
}
for i := 1; i*i <= n; i++ {
for j := i * i; j <= n; j++ {
dp[j] = utils.Min(dp[j], dp[j-i*i]+1)
}
}
return dp[n]
}
数学
依据：
由拉格朗日的四平方定理可得，每个自然数都可以表示为四个整数平方之和。
分析：
四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界即4。
四平方和定理可以推出三平方和推论：当且仅当n!=4^k*(8*m+7)时n可以被表示为至多三个正整数的平方和。
所以n=4^k*(8*m+7)时只能被表示为四个正整数的平方和。此时我们可以直接返回 4。当n!=4^k*(8*m+7)时需要判断 n 到底可以分解成几个完全平方数之和。答案肯定是 1，2，3 中的一个。
题目要求我们求最小的，所以从1开始一个个判断是否满足。如果答案为1，代表n为完全平方数，这很好判断。如果答案为 2，代表n=a^2+b^2，枚举1->根号n即可，如果还不满足那么就是3个。
// 执行耗时:0 ms,击败了100.00% 的Go用户
// 内存消耗:1.9 MB,击败了98.97% 的Go用户
func numSquaresFast(n int) int {
if isPerfectSquare(n) {
return 1
}
if checkAnswer4(n) {
return 4
}
for i := 1; i*i <= n; i++ {
j := n - i*i
if isPerfectSquare(j) {
return 2
}
}
return 3
}
// 判断是否为完全平方数
func isPerfectSquare(n int) bool {
sq := int(math.Floor(math.Sqrt(float64(n))))
return sq*sq == n
}
// 判断是否能表示为 4^k*(8m+7)
func checkAnswer4(x int) bool {
for x%4 == 0 {
x /= 4
}
return x%8 == 7
}
正如其介绍的那样，只有beats 100%的题解才会被放到这上面（当然仅限于Golang），所以如果你想知道的最优解或许可以参考这本书，它也仍在不断更新。
70.爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
分析
完全背包做法就是以步数作为物品{1, 2}来装满背包容量为n的方法有多少种，而且是求的排列数，顺序有关系
若题目将步数扩展为一次可以爬1、2、3、4…那么使用完全背包问题就很简单了，每次的阶数就是物品的重量
// 执行耗时:0 ms,击败了100.00% 的Go用户
// 内存消耗:1.9 MB,击败了21.29% 的Go用户
func climbStairsII(n int) int {
steps := []int{1, 2}
dp := make([]int, n+1)
dp[0] = 1
for i := 0; i <= n; i++ {
for j := range steps {
if i >= steps[j] {
dp[i] += dp[i-steps[j]]
}
}
}
return dp[n]
}
139.单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
分析
将单词看作是物品，字符串看为背包，单词能否组成字符串就是问物品能否将背包装满，同时单词可以重复使用那么就是完全背包问题；再同时因为单词的顺序会改变字符串，这里强调了顺序是有意义的，所以是求排列数。
综上，可以转换为一道求完全背包问题的排列数。
定义dp[i]为当字符串长度为i的时候可以拆分为一个或多个字典中的单词。
递推公式：如果dp[j]为true，s[j, i]也在字典里面那么dp[i]就为true，这里的s[j, i]就是一个单词。
求排列数，先遍历背包再遍历物品。
func wordBreak(s string, wordDict []string) bool {
//创建一个集合用来判断是否存在，单纯的set不方便判断是否存在
wordDictSet := make(map[string]bool)
for _, w := range wordDict {
wordDictSet[w] = true
}
dp := make([]bool, len(s)+1)
dp[0] = true
//排列数，外层遍历背包，内层遍历物品
for i := 1; i <= len(s); i++ {
for j := 0; j < i; j++ {
dp[i] = dp[j] && wordDictSet[s[j:i]]
//找到一组就不用再找了
if dp[i] {
break
}
}
}
return dp[len(s)]
}