问题描述:零钱兑换问题 现在有面额分别为1、2、5元的硬币数,总金额11元,计算并返回可以凑成总金额所需的最少硬币个数。若没有组合能组成总金额,则返回-1。给出采用递归法求解的解题思路以及重复计算的次数,要求画出递归图解过程。
时间: 2024-08-12 17:08:04 浏览: 102
零钱兑换问题,也称为找零问题,是一个经典的动态规划和递归问题。给定一定面额(例如1元、2元和5元硬币),目标是找出最少数量的硬币组合,以达到给定的总金额。这是一个贪心算法不适用的情况,因为不是总是使用最大面额的硬币能得到最少硬币数。
解题思路(递归方法):
1. 定义一个递归函数,比如`minCoins(amount, coins)`, 其中`amount`是剩余需要找零的金额,`coins`是一个列表,包含当前可用的硬币面额。
2. 基本情况:
- 如果`amount`为0,表示已经找到了足够的硬币组合,返回0,代表不需要额外硬币。
- 如果`amount`小于等于0,意味着已经有了更多的硬币(可能不需要),返回-1,表示无法组成给定金额。
3. 递归情况:
- 遍历硬币列表`coins`中的每个面额,对于每个面额`coin`,如果`amount`大于`coin`,尝试用一个`coin`替换部分或全部的`amount`,然后递归调用`minCoins(amount - coin, coins)`,加上1(表示当前硬币的数量)作为结果。
4. 返回最小的递归结果,即找到所有可行组合中硬币数最少的那个。
重复计算次数:
递归方法会重复计算很多相同的子问题,例如对于不同的剩余金额`amount`,可能会对每个硬币面额都进行同样的尝试。这种情况下,重复计算次数是指数级别的,因为每个递归调用会产生两个新的子问题。
递归图解过程:
你可以用一个树状结构来表示递归过程,根节点表示总金额,向下分支表示使用不同面额的硬币。每层代表一次递归,分支数对应当前可选的硬币面额,每个节点的值是剩余金额或结果(-1或硬币数)。由于有重叠子问题,部分路径会被多次遍历。
阅读全文