C++ 找零程序

在本文中，我们将看到最常被问到的面试问题。找零钱问题是动态规划方法的一个很好的例子。现在让我们来理解问题陈述。

问题陈述

给定 N 和一个包含一些数字（卢比硬币）的数组（例如 coins[]）。N 是一个硬币，数组包含各种硬币。任务是使用数组中的硬币找零 N。以使用最少硬币数量的方式找零。

示例

我们以输入数组 coins[] = {10, 25, 5}，总硬币数为 3 为例。

我们有 N = 30。

输出是二，因为我们可以使用一枚 25 卢比硬币和一枚 5 卢比硬币来凑成 30。(25 + 5 = 30)

同样，coins[] = {1, 9, 6, 5}，总硬币数为 4。

N = 13。

输出是三，因为我们需要两枚 6 卢比硬币和一枚 1 卢比硬币。(6 + 6 + 1 = 13)

方法 1

该方法使用递归方法。我们从 N 开始，在每次迭代中，我们将问题分解为更小的子问题。这是通过从硬币数组中取出每个硬币并从 N 中减去它来完成的。当 N 变为零时，我们得到所需的解决方案。为了获得最佳答案，我们返回所有组合中的最小值。

C++ 代码

输出

Minimum coins needed are 2

上述解决方案不适用于更大的输入。在这种情况下，递归方法会失败。

现在让我们看看一种优化的方法。

方法 2

这种方法利用了自下而上的动态规划思想。

由于子问题会反复计算，因此存在重叠子问题的情况。重新计算的问题可以通过记忆化的特性来解决，即创建一个 dp[] 数组，用于存储特定阶段计算出的值。在每个阶段计算所有可能的组合。在所有组合之后，dp[] 数组中的最后一个值就是我们的答案。

C++ 代码

输出

Minimum coins needed are 2

代码的时间复杂度是 O(total_coins + sum)。由于在每个阶段存储结果并在其他迭代中利用它，这是一种非常优化的方法。