Dynamic Programming - 322. Coin Change

322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3 Output: -1

Note: You may assume that you have an infinite number of each kind of coin.

思路：

这是一道经典的动态规划最值问题，和279题很像，题目意思是换零钱，比如求的总额为A，那么最后一步就是求出置换A需要最少的硬币，如果存在一个数B，满足B + coins[i] = A，（0<= i <= len(coins)-1），那么A的最少置换硬币数就变成B的最少置换硬币数+1，子问题就变成求B，所以状态转移方程就变成dp[i] = min{dp[i - coins[j]] + 1}, for all j,初始条件就是dp[0],因为没有dp[0]是不能通过状态转移方程求出来。而初始值，可以设置为一个最大值，这样就能取最小值。

代码：

go：

func coinChange(coins []int, amount int) int {

    dp := make([]int, amount+1)
    n := len(coins)
    
    // initialization
    dp[0] = 0;
    
    for i := 1; i <= amount; i++ {
        dp[i] = math.MaxInt32
        for j := 0; j < n; j++ {
            if i >= coins[j] && dp[i - coins[j]] != math.MaxInt32{
                dp[i] = min(dp[i - coins[j]] + 1, dp[i])
            }
        } 
    }
    
    if dp[amount] == math.MaxInt32 {
        dp[amount] = -1
    }
    
    return dp[amount]
}

func min(i, j int) int {
    if i < j {
        return i
    }
    return j
}