问题描述:零钱兑换问题 现在有面额分别为1、2、5元的硬币数,总金额11元,计算并返回可以凑成总金额所需的最少硬币个数。若没有组合能组成总金额,则返回-1。给出采用递归法求解的解题思路以及重复计算的次数,要求画出递归图解过程。
时间: 2024-08-12 07:07:51 浏览: 96
零钱兑换问题是一个经典的动态规划问题,通常用于练习递归算法和优化策略。目标是使用给定的硬币面额(例如1元、2元和5元)来凑出指定的总金额(如11元),同时找到所需的最小硬币数量。这个问题可以使用回溯(也称递归)的方法来解决。
**解题思路:递归法**
1. 定义状态:设 `dp[i]` 表示使用给定面额的硬币能够凑出 `i` 元所需的最小硬币数量。初始状态 `dp = 0`,因为不需要任何硬币来凑0元。
2. 递归规则:对于每个 `i`(从1到总金额),尝试用三种面额中最小的一种来替换 `i` 元,然后更新 `dp[i]` 的值。具体步骤如下:
a. 如果 `i` 是某个面额的倍数,直接用该面额的硬币,即 `dp[i] = dp[i - coin_value] + 1`,这里 `coin_value` 是1, 2或5。
b. 否则,寻找小于 `i` 的最大面额 `j`(例如5),尝试将 `j` 添加到已有的解决方案中,即 `dp[i] = min(dp[i], dp[i - j] + 1)`。
3. 递归结束条件:当 `i` 大于总金额时,返回 `dp[i]`,否则继续递归直到 `i` 为0。
**重复计算次数和递归图解过程:**
递归过程中存在大量的重复计算,比如多次尝试用1元硬币凑11元的情况。可以利用记忆化搜索(动态规划)来避免重复计算。在每个状态 `dp[i]` 记录之前的结果,只有在首次访问时才会计算。
在递归图解过程中,通常会画出一个表格(类似数组),其中行代表金额,列代表可用的面额,然后填充递推过程中的 dp 值。从左上角开始,通过横向和纵向的递推,逐步填充整个表格。每个格子的填充都是基于左上角到当前位置的最小子集解决方案。
阅读全文