322.M 零钱兑换

Problem: 322. 零钱兑换

[TOC]

思路

动态规划。

设dp[i]为组成金额i所需要的最大硬币数，则：

dp[i] = min(dp[i - coin[j]]) + 1, 对于 j ∈ [0, len(coints)), 左开又闭区间

Code

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		dp[i] = amount + 1 //不能设置初始值为极大值，否则+1后就变成极小值了
		for j := 0; j < len(coins); j++ {
			if coins[j] <= i {
				dp[i] = min(dp[i], dp[i-coins[j]]+1)
			}
		}
	}

	if dp[amount] > amount {
		return -1
	}

	return dp[amount]
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}