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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param aim int整型 the target
 * @return int整型
*/
// 记忆化搜索树；自上而下进行查询搜索; 递归的方法
func recursionMinMoney(arr []int, dp map[int]int, tAim int) int {
	if tAim < 0 {
		return -1
	}
	if tAim == 0 {
		return 0
	}
	if v, ok := dp[tAim]; ok {
		return v
	}
	res := -1
	for _, v := range arr {
		tmp := recursionMinMoney(arr, dp, tAim-v)
		if res == -1 || (res > tmp && tmp != -1) {
			res = tmp
		}
	}
	if res == -1 {
		dp[tAim] = -1
	} else {
		dp[tAim] = res + 1
	}
	return dp[tAim]
}
func minMoney(arr []int, aim int) int {
	// write code here
	dp := make(map[int]int, 0)
	for _, v := range arr {
		dp[v] = 1
	}
	minV := recursionMinMoney(arr, dp, aim)
	return minV
}