题目:
题解:
func coinChange(coins []int, amount int) int {var (dfs func(x int) int // x金额 最少硬币个数memo = make(map[int]int) // 记忆化)dfs = func(x int) int {//边界if x == 0 {return 0} else if x < 0 {return math.MaxInt32}//记忆化if _, ok := memo[x]; ok {return memo[x]}//状态转移var res = math.MaxInt32for _, y := range coins {res = min(res, 1+dfs(x-y))}memo[x] = resreturn res}ans := dfs(amount)if ans == math.MaxInt32 {return -1}return ans
}