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]
}