首页 🍒LeetCode,🐶算法

题目

0.png

思路

经典DP。

dp[i]:兑换i最少需要多少个硬币。
确定基本状态:dp[0] = 0
状态转移:想要得到amount需要的最少硬币,如果知道了dp[amount-1]的数量,那dp[amount]即为dp[amount-1] + 1(加上一个一元的硬币),然后遍历coins,找到需要硬币数最少的那个硬币。

func coinChange(coins []int, amount int) int {
    sort.Ints(coins)
    dp := make([]int, amount + 1)
    for i := range dp {
        dp[i] = amount + 1
    }
    dp[0] = 0
    for i := 1; i < len(dp); i++ {
        for _, v := range coins {
            if i < v {
                break
            }
            dp[i] = min(dp[i], 1 + dp[i-v])
        }
    }
    if dp[amount] == amount + 1 {
        return -1
    }
    return dp[amount]
}

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



文章评论