代码随想录二刷Day44

今日任务

完全背包
518.零钱兑换 II
377.组合总和 Ⅳ
语言：Go

完全背包

1. 定义：有N件物品和一个最多能背重量为W的背包，第i件物品的重量是weight[i]，得到的价值是value[i]，每件物品都有无限个（可以放入背包多次）
2. 遍历顺序：使用一维数组时，先遍历物品还是背包都是可以的，内层要从小向大遍历（因为物品有无限个）
3. 先遍历物品，后遍历背包：组合数
   先遍历背包，后遍历物品：排列数

518. 零钱兑换 II

链接：https://leetcode.cn/problems/coin-change-ii/
二维数组

func change(amount int, coins []int) int {//dp[i][j]表示从前i种硬币中取，能凑成金额为j的组合有dp[i][j]种dp := make([][]int, len(coins) + 1)for i := 0; i <= len(coins); i++ {dp[i] = make([]int, amount + 1)}for i := 0; i <= len(coins); i++ {dp[i][0] = 1}for i := 0; i < len(coins); i++ {for j := 1; j <= amount; j++ {if j < coins[i] {dp[i + 1][j] = dp[i][j]} else {dp[i + 1][j] = dp[i][j] + dp[i + 1][j - coins[i]]}}}return dp[len(coins)][amount]
}/*0   1   2   3   4   50   1   0   0   0   0   01   1   1   1   1   1   12   1   1   2   2   3   35   1   1   2   2   3   4
*/

一维数组

func change(amount int, coins []int) int {//dp[j]表示能凑成金额为j的组合有dp[j]种dp := make([]int, amount + 1)dp[0] = 1for i := 0; i < len(coins); i++ {for j := coins[i]; j <= amount; j++ {dp[j] += dp[j - coins[i]]}}return dp[amount]
}

377. 组合总和 Ⅳ

链接：https://leetcode.cn/problems/combination-sum-iv/

func combinationSum4(nums []int, target int) int {dp := make([]int, target + 1)dp[0] = 1for j := 0; j <= target; j++ {for i := 0; i < len(nums); i++ {if j >= nums[i] {dp[j] += dp[j - nums[i]]}}}return dp[target]
}