换零钱

type
status
date
slug
summary
tags
category
icon
password
用100元来换若干面值的零钱（1，5，10，25，50），有多少种兑换方式？

思路

定义一个函数f(amount,coins)，用来计算使用coins来换amount的方案数量。很容易得到，分为两种情况
  1. 使用零钱A（至少使用1次A）
  1. 不使用零钱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:])
得到如下等式：
递归退出
  1. 当可供使用的零钱列表coins已经为空
    1. 还需要兑换的金额amount为0，说明该路径兑换成功
    2. amount不为0，说明兑换失败
  1. coins不为空
    1. 当需要兑换的金额amount为负数的时候，说明该情况下兑换已经失败了。
    2. amount非负，继续兑换

代码

推广

这个思路也可以放到另外一个子集问题上，找到集合（无重复元素，即SET）的所有子集。很容易得到：
SET的所有子集 等于 SET[1:]的所有子集 加上 SET[1:]的所有子集每个都加上SET[0]
Loading...

© XGFan 2012-2025