题解 | 兑换零钱(一)

package main

import (
	"sort"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param aim int整型 the target
 * @return int整型
 */
func minMoney( arr []int ,  aim int ) int {
    // write code here
    dp := make([]int, aim+1)
    for i := range dp {
        dp[i] = 1 << 31
    }
    dp[0] = 0

    sort.Ints(arr)

    for _,coin := range arr {
        for j := coin;j<=aim;j++{
            dp[j] = min(dp[j],dp[j-coin]+1)
        }
    }
    if dp[aim] == 1 << 31 {
        return -1
    }


    return dp[aim]
}

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