- 暴力递归
func coinChange(coins []int, amount int) int { | |
return dp(coins, amount) | |
} | |
func dp(conis []int,amount int) int { | |
if amount == 0 { | |
return 0 | |
} | |
if amount < 0 { | |
return -1 | |
} | |
res := math.MaxInt32 | |
for _, v := range coins { | |
subProblem := dp(coins, amount-v) | |
if subProblem == -1 { | |
continue | |
} | |
res = min(res, subProblem+1) | |
} | |
if res == math.MaxInt32 { | |
return -1 | |
} | |
return res | |
} | |
func min(a, b int) int { | |
if a < b { | |
return a | |
} | |
return b | |
} |
- 带备忘录的递归
func coinChange(coins []int, amount int) int { | |
memo := make([]int, amount+1) | |
for i := 0; i < len(memo); i++ { | |
memo[i] = -666 | |
} | |
return dp(coins, amount, memo) | |
} | |
func dp(coins []int,amount int,memo []int) int { | |
if amount == 0 { | |
return 0 | |
} | |
if amount < 0 { | |
return -1 | |
} | |
if memo[amount] != -666 { | |
return memo[amount] | |
} | |
res := math.MaxInt32 | |
for _, v := range coins { | |
subProblem := dp(coins, amount-v, memo) | |
if subProblem == -1 { | |
continue | |
} | |
res = min(res, subProblem+1) | |
} | |
if res == math.MaxInt32 { | |
memo[amount] = -1 | |
}else { | |
memo[amount] = res | |
} | |
return memo[amount] | |
} | |
func min(a, b int) int { | |
if a < b { | |
return a | |
} | |
return b | |
} |
- 动态规划
func coinChange(coins []int, amount int) int { | |
//dp 数组的定义：当目标金额为 i 时，至少需要 dp [i] 枚硬币凑出 | |
dp := make([]int,amount+1) | |
//dp 数据中的值都初始化为 amount+1, 因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount+1 就相当于初始化为正无穷，便于后续取最小值。 | |
// 为什么不直接初始化为 int 型的最大值 Integer.MAX_VALUE 呢？因为后面有 dp [i - coin] + 1，这就会导致整型溢出。 | |
for i := range dp{ | |
dp[i] = amount + 1 | |
} | |
dp[0] = 0 | |
for i := 0; i < len(dp); i++{ | |
for _,coin := range coins{ | |
if i - coin < 0{ | |
continue | |
} | |
dp[i] = min(dp[i],1+dp[i - coin]) | |
} | |
} | |
if dp[amount] == amount+1{ | |
return -1 | |
} | |
return dp[amount] | |
} | |
func min(a, b int) int { | |
if a < b { | |
return a | |
} | |
return b | |
} |
