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

package main

/**
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param aim int整型 the target
 * @return int整型
*/
func minMoney( arr []int ,  aim int ) int {
    if aim==0{return 0}
    // dp[n]=dp[n-m]+1
    dp:=make([]int,aim+1)
    for i:=0;i<len(arr);i++{
        if aim>arr[i]{
            dp[arr[i]]=1
        }
    }

    for i:=1;i<=aim;i++{
        for j:=0;j<len(arr);j++{
            money:=arr[j]
            if i>=arr[j]{
                pre:=dp[i-money]
                if pre==0{
                    continue
                }else if dp[i]==0{
                    dp[i]=pre+1
                }else if dp[i]!=0{
                    dp[i]=min(pre+1,dp[i])
                }
            }
        }
    }
    if dp[aim]==0{
        return -1
    }else{
        return dp[aim]
    }
}

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