【算法】在各种排列组合下，计算零钱找零方式数量

算法,各种,排列组合,计算,零钱,找零,方式,数量 · 浏览次数 : 29

小编点评

```csharp public static int CountCombinations(int amount, int[] coins) { // 创建一个大小为 amount+1 的数组 dp，用于存储组合数量 int[] dp = new int[amount + 1]; // 初始化 dp[0] 为 1，表示金额为 0 时只有一种组合方式 dp[0] = 1; // 遍历硬币数组 foreach (int coin in coins) { // 遍历每个硬币，从硬币的面值开始遍历到目标金额 for (int i = coin; i <= amount; i++) { // 更新 dp[i]，将之前的组合数量加上使用当前硬币 coin 后的组合数量 dp[i] += dp[i - coin]; } } // 返回目标金额 amount 对应的组合数量 return dp[amount]; } ``` **测试用例：** ```csharp [Test] public void CountCombinations_Example1_Returns3() { Assert.AreEqual(3, Kata.CountCombinations(4, new[] { 1, 2 })); } [Test] public void CountCombinations_Example2_Returns4() { Assert.AreEqual(4, Kata.CountCombinations(10, new[] { 5, 2, 3 })); } [Test] public void CountCombinations_Example3_Returns0() { Assert.AreEqual(0, Kata.CountCombinations(11, new[] { 5, 7 })); } [Test] public void CountCombinations_NoCoins_Returns1() { Assert.AreEqual(1, Kata.CountCombinations(0, new int[] { })); } [Test] public void CountCombinations_LargeAmount_ReturnsExpectedResult() { Assert.AreEqual(292, Kata.CountCombinations(100, new[] { 1, 2, 5, 10, 20, 50 })); } ```

正文

写一个函数，在给定一系列硬币面额的情况下，计算你可以用多少种不同的方式来兑换一笔钱。

例如，如果你有面额为1和2的硬币，有3种方法可以为4找零：

1+1+1+1，1+1+2，2+2。

硬币的顺序无关紧要：

1+1+2==2+1+1

此外，假设你有无限数量的硬币。

示例调用，一个金额和一系列独特面额的硬币：

CountCombinations(4, new[] {1,2}) // => 3

CountCombinations(10, new[] {5,2,3}) // => 4

CountCombinations(11, new[] {5,7}) // => 0

算法实现：

 1 using System;
 2 
 3 public static class Kata
 4 {
 5     public static int CountCombinations(int amount, int[] coins)
 6     {
 7         int[] dp = new int[amount + 1]; // 创建一个大小为 amount+1 的数组 dp，用于存储组合数量
 8         dp[0] = 1; // 初始化 dp[0] 为 1，表示金额为 0 时只有一种组合方式
 9 
10         foreach (int coin in coins) // 遍历硬币数组
11         {
12             for (int i = coin; i <= amount; i++) // 对于每个硬币，从硬币的面值开始遍历到目标金额
13             {
14                 dp[i] += dp[i - coin]; // 更新 dp[i]，将之前的组合数量加上使用当前硬币 coin 后的组合数量
15             }
16         }
17 
18         return dp[amount]; // 返回目标金额 amount 对应的组合数量
19     }
20 }
21 /*这段代码使用动态规划来解决问题。它维护了一个名为 dp 的数组，其中 dp[i] 表示金额为 i 时的组合数量。代码通过遍历硬币数组，
22   并在每个硬币面值开始的位置到目标金额之间进行更新，以获得最终的组合数量。最后，返回目标金额 amount 对应的组合数量。*/

测试用例:

 1 using NUnit.Framework;
 2 
 3 [TestFixture]
 4 public class KataTests
 5 {
 6     [Test]
 7     public void CountCombinations_Example1_Returns3()
 8     {
 9         int result = Kata.CountCombinations(4, new[] { 1, 2 });
10         Assert.AreEqual(3, result);
11     }
12 
13     [Test]
14     public void CountCombinations_Example2_Returns4()
15     {
16         int result = Kata.CountCombinations(10, new[] { 5, 2, 3 });
17         Assert.AreEqual(4, result);
18     }
19 
20     [Test]
21     public void CountCombinations_Example3_Returns0()
22     {
23         int result = Kata.CountCombinations(11, new[] { 5, 7 });
24         Assert.AreEqual(0, result);
25     }
26 
27     [Test]
28     public void CountCombinations_NoCoins_Returns1()
29     {
30         int result = Kata.CountCombinations(0, new int[] { });
31         Assert.AreEqual(1, result);
32     }
33 
34     [Test]
35     public void CountCombinations_LargeAmount_ReturnsExpectedResult()
36     {
37         int result = Kata.CountCombinations(100, new[] { 1, 2, 5, 10, 20, 50 });
38         Assert.AreEqual(292, result);
39     }
40 }
41 /*
42 这里设计了5个测试用例来测试 `CountCombinations` 方法的功能和正确性。第一个测试用例是例子中给出的第一个示例，测试返回值是否等于 3。
43 第二个测试用例是例子中给出的第二个示例，测试返回值是否等于 4。第三个测试用例是例子中给出的第三个示例，测试返回值是否等于 0。
44 第四个测试用例测试当没有硬币时，返回值是否等于 1。第五个测试用例测试一个较大的金额，验证返回值是否符合预期。*/