要點
- 簡化問題
- 減少計算量
套路
- 定義狀態(tài)
- 定義動作
- 定義邊界
- 緩存已知
硬幣找零問題
問題：有三種面值硬幣1,3,5倦逐，且無限量，請問共需要找零n元，最少需要幾枚硬幣檬姥？
定義狀態(tài)：minCoinNum(n), 即n元需要的最小硬幣數(shù)目曾我。
定義動作（分而治之）：假如我知道了minCoinNum(n-1)、minCoinNum(n-3)健民、minCoinNum(n-5)的最少硬幣數(shù)目抒巢，則為n元時，最少硬幣數(shù)目為：min(minCoinNum(n-1)+1, minCoinNum(n-3)+1, minCoin(n-5)+1)秉犹。將n元分為n-1元蛉谜、n-3元、n-5元崇堵，然后選擇一個最小的方案型诚。
定義邊界：當n<1時，沒有余額 鸳劳，需要0個硬幣狰贯，當n等于1、3赏廓、5時涵紊，需要1個硬幣。
緩存已知：minCoinNum(n)作為可能多次計算的數(shù)值幔摸，由于每次計算都一樣摸柄，可以將結(jié)果緩存起來，避免不必要的計算既忆。
簡單的遞歸版本（無緩存已知的計算狀態(tài)）代碼
package main
import "math"
var coins []int64
func init() {
coins = []int64{5, 3, 1}
}
func coinSum(amount int64) int64 {
if amount < 1 {
return 0
}
var minNum int64 = math.MaxInt64
for _, v := range coins {
if amount < v {
continue
}
if amount == v {
return 1
}
minNum = int64(math.Min(float64(minNum), float64(coinSum(amount-v)+1)))
}
return minNum
}
func main() {
var amount int64 = 7
println(coinSum(amount))
}
