322. Coin Change

CoinChange.cs

public class Solution {
 public int CoinChange(int[] coins, int amount){
    var dp = new int[amount + 1];
    Array.Fill(dp, int.MaxValue);
    dp[0] = 0;
    
    foreach(var coin in coins){
      for(var change = 1; change <= amount; change++){
        if(coin > change || dp[change - coin] == int.MaxValue)
          continue;
        dp[change] = Math.Min(dp[change], 1 + dp[change - coin]);
      }
    }
    return dp[dp.Length - 1] == int.MaxValue ? -1 : dp[dp.Length - 1];
  }
  public int CoinChangeRec(int[] coins, int amount) {
    var memo = new int?[amount];
    int CountDp(in int n){
      if(n == 0)
        return 0;
      if(n < 0)
        return -1;
      if(memo[n - 1].HasValue)
        return memo[n - 1].Value;
      var counter = int.MaxValue;
      foreach(var coin in coins) {
        var current = CountDp(n - coin);
        if(current >= 0 && current < counter)
          counter = Math.Min(counter, 1 + current);
      }
      memo[n - 1] = counter == int.MaxValue ? -1 : counter;
      return memo[n - 1].Value;
    }
    var res = CountDp(amount);
    return res == int.MaxValue ? -1 : res;
  }
}