要点
- 简化问题
- 减少计算量
套路
- 定义状态
- 定义动作
- 定义边界
- 缓存已知
硬币找零问题
问题：有三种面值硬币1,3,5，且无限量，请问共需要找零n元，最少需要几枚硬币？
定义状态：minCoinNum(n), 即n元需要的最小硬币数目。
定义动作（分而治之）：假如我知道了minCoinNum(n-1)、minCoinNum(n-3)、minCoinNum(n-5)的最少硬币数目，则为n元时，最少硬币数目为：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)作为可能多次计算的数值，由于每次计算都一样，可以将结果缓存起来，避免不必要的计算。
简单的递归版本（无缓存已知的计算状态）代码
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))
}
