用100元来换若干面值的零钱(1,5,10,25,50),有多少种兑换方式?

思路

定义一个函数\(f(amount,coins)\),用来计算使用coins来换amount的方案数量。很容易得到,分为两种情况

  1. 使用零钱A(至少使用1次A)
  2. 不使用零钱A

情况1,至少使用1次A,coins来兑换amount 等价于 至少使用0次A,coins来兑换(amount-A) 等价于 coins来兑换(amount-A) ,可以表示为 f(amount-coins[0],coins)

情况2,不实用零钱A,可以从coins中移除掉A,表示为 f(amount,coins[1:])

得到如下等式:

f(amount,coins) = f(amount-coins[0],coins) + f(amount,coins[1:])

递归退出

  1. 当可供使用的零钱列表coins已经为空
    1. 还需要兑换的金额amount为0,说明该路径兑换成功
    2. amount不为0,说明兑换失败
  2. coins不为空
    1. 当需要兑换的金额amount为负数的时候,说明该情况下兑换已经失败了。
    2. amount非负,继续兑换

代码

func change(amount int, coins []int) int {
	if len(coins) == 0 {
		if amount != 0 {
			return 0
		} else {
			return 1
		}
	}
	if amount < 0 {
		return 0
	}
	return change(amount-coins[0], coins) + change(amount, coins[1:])
}
(define (change amount coins)
  (cond ((= 0 (length coins))
         (if (= 0 amount)
             1
             0))
        ((> 0 amount) 0)
        (else (+ (change (- amount (car coins)) coins)
                 (change amount (cdr coins))))))

推广

这个思路也可以放到另外一个子集问题上,找到集合(无重复元素,即SET)的所有子集。很容易得到:

SET的所有子集 等于 SET[1:]的所有子集 加上 SET[1:]的所有子集每个都加上SET[0]

f(set) = f(set[1:]) + map(f(set[1:]),x -> [..x,set[0]])
fun f(l: List<Any>): List<List<Any>> = l.getOrNull(0)?.let { first ->
   val subsets = f(l.subList(1, l.size))
   subsets + subsets.map { it + first }
} ?: listOf(emptyList())