[代码随想录]Day38-动态规划part06-526互联

题目：518. 零钱兑换 II

思路：

第二层for正向d就是可以无限次使用(不会重复出现：1,1,2和2,1,1是一种情况)

代码：

func change(amount int, coins []int) int {
    dp := make([]int, amount + 1)
    dp[0] = 1
    for i:=0; i < len(coins); i++ {
        for j:=coins[i]; j <= amount; j++ {
            dp[j] += dp[j-coins[i]]
        }
    }
    return dp[amount]
}

参考：

代码随想录

题目：377. 组合总和 Ⅳ

思路：

先遍历容量再遍历物品的话 1,1,2和2,1,1是两种情况

代码：

func combinationSum4(nums []int, target int) int {
    dp := make([]int, target + 1)
    dp[0] = 1
    for j := 0; j <= target; j++ { // 遍历背包容量
        for i := 0; i < len(nums); i++ { // 遍历物品
            if (j - nums[i] >= 0) {
                dp[j] += dp[j - nums[i]]
            }
        }
    }
    return dp[target]
}

参考：