代码随想录算法训练营|day45

322.零钱兑换

dp[i]表示凑成i所需的最少零钱个数
(1)先遍历物品，后遍历背包

func coinChange(coins []int, amount int) int {
	maxAmount := amount + 1
	dp := make([]int, amount+1)
	for i := 0; i <= amount; i++ {
		dp[i] = maxAmount
	}
	dp[0] = 0
	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			dp[i] = min(dp[i-coin]+1, dp[i])
		}
	}
	if dp[amount] != maxAmount {
		return dp[amount]
	} else {
		return -1
	}
}

(2)先遍历背包，后遍历物品

	for i := 1; i <= amount; i++ {
		for j := 0; j < len(coins); j++ {
			if i >= coins[j] {
				dp[i] = min(dp[i], dp[i-coins[j]]+1)
			}
		}
	}

279.完全平方数

dp[i]表示凑成平方和为i的最小元素个数
初始化：因为找最小个数，所以初始化为最大值，凑成平方和为0的最小元素个数为0
(1)先遍历物品，后遍历背包

func numSquares(n int) int {
	dp := make([]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = math.MaxInt
	}
	dp[0] = 0
	for i := 1; i*i <= n; i++ {
		for j := i * i; j <= n; j++ {
			dp[j] = min(dp[j], dp[j-i*i]+1)
		}
	}
	return dp[n]
}

(2)先遍历背包，后遍历物品

	for i := 1; i <= n; i++ {
		for j := 1; j*j <= i; j++ {
			dp[i] = min(dp[i], dp[i-j*j]+1)
		}
	}

代码随想录文章详解

70.爬楼梯(进阶)
322.零钱兑换
279.完全平方数

总结

分清楚背包问题类型，背包和物品分别是啥，求解很容易
先遍历物品，后遍历背包：背包容量肯定要大于等于物品，小于等于最大背包容量(背包容量从物品起)
先遍历背包，后遍历物品：物品必须能装进背包里(物品小于背包容量)