题解 | #兑换零钱(一)#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param aim int整型 the target
 * @return int整型
*/
func minMoney( arr []int ,  aim int ) int {
    // write code here
    // 定义 dp[i] 为组成金额 i 需要的最少货币数
    // 求解组成aim的最少的货币数
    // dp[i] = min(dp[i],dp[i-arr[j]]+1)
    if aim == 0 {
        return 0
    }

    // 初始化dp数组，金额i需要的最少货币数为dp[i]
    dp := make([]int, aim + 1)
    for i := range dp {
        dp[i] = aim + 1
    }
    dp[0] = 0 // 组成金额0需要0张货币 

    for i := 0; i < len(arr);i++ {
        for j := arr[i]; j <= aim; j++ {
            
            dp[j] = min(dp[j],dp[j-arr[i]] + 1)
        }     
    }

    if dp[aim] == aim + 1 {
        return -1
    }

    return dp[aim]
 }

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