leetcode 322. 零钱兑换 golang实现

描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。

示例1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1
           

思路

跟之前动态规划求最小值的题目异曲同工，比如 279.完全平方数这道题

1. 找公式
dp[i]表示 金额为i的最小硬币个数
转移方程为: dp[i] = dp[i - coin] + 1
这个方程是有条件的 即 金额要大于硬币金额 并且dp[i - coin]是有效的 因为无效的话 dp[i-coin] = -1 
2. 初始值
设置dp[i] = i 因为硬币最小金额为1 所以dp[i] 最大也就是i
           

实现

func CoinChange(coins []int, amount int) int {
	dp := make([]int, amount + 1)

	for i := 1; i <= amount; i++{
		dp[i] = i       // dp[i] 最大值为i
		found := false  // 表示dp[i] 是否有效
		for _, coin := range coins{
			if coin <= i && dp[i-coin] >= 0{
				dp[i] = Min(dp[i], dp[i-coin] + 1)
				found = true
			}
		}

		if !found {
			dp[i] = -1
		}
	}

	return dp[amount]
}