[C#] 凑零钱解法

假设 k=3 面值为 1 、 2 、 5 总金额 amount = 11 想要知道最少硬币解法

    static void Main(string[] args)    {        CoinChangeFuntion();         }          private static void CoinChangeFuntion()  {      var coins = new List<int>      {          1,          2,          5      };      int amount = 11;      Console.WriteLine(CoinChange(coins, amount));  }  private static int CoinChange(List<int> coins, int amount)  {      if (amount == 0) return 0;      int[] dp = new int[amount + 1];      Array.Fill(dp, int.MaxValue);      dp[0] = 0;      for (int i = 1; i <= amount; i++)      {          foreach (int coin in coins)          {              if (i - coin >= 0 && dp[i - coin] != int.MaxValue)              {                  dp[i] = Math.Min(dp[i], dp[i - coin] + 1);              }          }      }      return dp[amount] == int.MaxValue ? -1 : dp[amount];  }

解题重点在于依序找出金额 0 ~ 11 最少的硬币解法如下
注: dp[0] 里面的 0 指的是金额
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
dp[4] = 2;
dp[5] = 1;
dp[6] = 2;
dp[7] = 2;
dp[8] = 3;
dp[9] = 3;
dp[10] = 2;
dp[11] = 3;

假设 i 是 11（表示我们目前正在尝试组成金额 11），并且假设我们正在处理面值为 2 的硬币。这时，i - coin 就是 11 - 2，等于 8。
这时候我们可以看 金额 dp[8] 最少的硬币解法为 3 那 组成金额 11 最少的硬币解法为 处理面值 2 (1枚硬币) + 金额 8 元 (3枚硬币) = 4 枚硬币

当 for 迴圈中的 i 是 11（表示我们目前正在尝试组成金额 11），并且假设我们正在处理面值为 5 的硬币。这时，i - coin 就是 11 - 5，等于 6。
这时候我们可以看 金额 dp[6] 最少的硬币解法为 2 那 组成金额 11 最少的硬币解法为 处理面值 5 (1枚硬币) + 金额 6 元 (2枚硬币) = 3 枚硬币

上述条件中 如果选择面值为 2 的硬币为 4 枚 选择面值为 5 的硬币为 3 枚 所以需要使用 Math.Min 取得最少硬币数量

dp[i] = Math.Min(dp[i], dp[i - coin] + 1); 这行确保 dp[i]（组成金额 i 所需的最少硬币数量）是最小的可能值