题解 | #换钱的最少货币数#

/**
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param aim int整型 the target
 * @return int整型
*/
func minMoney( arr []int ,  aim int ) int {
    // write code here
    // 定义一个最大值
    max := aim + 1

//  dp[i]含义 目标金额为i使，需要最少的兑换数量 
//  aim+1是指 从0元开始到aim元为止的位置
    dp := make([]int, aim+1)

//  dp中每一个数初始化为最大值
    for i:=0; i<len(dp); i++{
        dp[i] = max
    }
//  目标金额为0时， 不需要兑换，所以为0
    dp[0] = 0

    // 从金额1开始到目标金额aim，来对dp进行填充
    for i:=1; i<= aim; i++{
        // 能兑换的金额数组
        for j := 0; j < len(arr); j++{
            // 当前的目标金额为i
            // 当前金额小于等于目标金额的话，就可以兑换
            // dp[i-arr[j]]+1
            // dp[i-arr[j]] 
            //因为金额i 兑换了arr[j]元一张(所以+1)，剩下的金额就是 i-arr[j]
            // 金额 i-arr[j] 的最小兑换数 就是 dp[i-arr[j]]
            if arr[j] <= i {
                dp[i] = min(dp[i], dp[i-arr[j]]+1)
            }
        }
    }

    // 等于max说明，不能兑换
    if dp[aim] == max {
        return -1
    }
    return dp[aim]
}

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