day 38 | ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ

518. 零钱兑换 II

这道题就是完全背包问题，因为可以选择的数量是无限的。所以第二层的遍历顺序就是从前往后。
因为是次数问题，递推公式是 += 的，初值应该设定为dp【0】 = 1，否则无法进行累加。

func change(amount int, coins []int) int {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. 组合总和 Ⅳ

由于是组合问题，所以前后两个循环的顺序是相反的
由于是求次数，所以dp【0】 = 1
由于是次数，所以递推公式是 +=

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