322. 零钱兑换.md

322. 零钱兑换

题目传送门

点击这里

解题思路

这道题由于不限制硬币的数量，所以这道题是个完全背包问题。至于动态规划，最需要考虑的就是状态转移方程和起始状态，我们定义动态规划数组dp[i]表示凑够i块钱所需金币的最小个数，所以我们可以推出状态转移方程，假设使用了第j个金币一块，那么状态转移方程即为dp[i] = min(dp[i-coins[j]]+1, dp[i])，而初始状态的话，dp[0] = 0

代码

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    // 初始化
    dp[0] = 0
    for j := 1;j <= amount;j ++ {
        dp[j] = math.MaxInt32
    }


    // 遍历所有的金币数额,这道题和遍历的顺序没有关系
    for i := 0;i < len(coins);i ++ {
        if coins[i] <= amount {
            dp[coins[i]] = 1
        }
        // 由于是完全背包问题,所以从当前状态之后一直想后进行
        for j := coins[i]+1;j <= amount;j ++ {
            if dp[j-coins[i]] != math.MaxInt32 {
                // 这一步其实也可以做到了第二步初始化
                dp[j] = min(dp[j], dp[j-coins[i]]+1)
            }
        }
    }
    if dp[amount] == math.MaxInt32 {
        return -1
    }
    return dp[amount]
}

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

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    // 初始化
    dp[0] = 0
    // 先遍历背包也可以
    for j := 1;j <= amount;j ++ {
        dp[j] = math.MaxInt32
        for i := 0;i < len(coins);i ++ {
            if j >= coins[i] && dp[j-coins[i]] != math.MaxInt32 {
				// 推导公式
				dp[j] = min(dp[j], dp[j-coins[i]]+1)
            }
        }
    }

    if dp[amount] == math.MaxInt32 {
        return -1
    }
    return dp[amount]
}

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