02.凑零钱问题

先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：

// coins 中是可选硬币面值，amount 是目标金额
int coinChange(int[] coins, int amount);

1、暴力解法

public int CoinChange(List<int> coins, int amount)
{
    //base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    var res = int.MaxValue;

    foreach (var coin in coins)
    {
        var subproblem = CoinChange(coins, amount - coin);
        //子问题无解直接跳过
        if (subproblem == -1) continue;

        if (1 + subproblem < res)
            res = 1 + subproblem;
    }

    if (res == int.MaxValue) return -1;
    return res;
}

2、带备忘录的递归

public int CoinChange(List<int> coins, int amount)
{
    var dic=new Dictionary<int,int>();
    return Helper(dic, coins, amount);
}

public int Helper(Dictionary<int,int> dic,List<int> coins,int amount)
{
    if (dic.ContainsKey(amount)) return dic[amount];

    //base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    var res = int.MaxValue;
    foreach (var coin in coins)
    {
        var subproblem = Helper(dic, coins, amount - coin);
        if(subproblem==-1) continue;

        if (subproblem + 1 < res) res = subproblem + 1;
    }

    //返回值前，先向备忘录添加数据
    if (res == int.MaxValue) dic[amount] = -1;
    else dic[amount] = res;

    return dic[amount];
}

3、dp 数组的迭代解法

 public int CoinChange(List<int> coins, int amount)
{
    //数组大小为amount+1,初始值设置为amount+1
    var dp = new int[amount + 1];
    for (var i = 0; i < dp.Length; i++) dp[i] = amount + 1;
    //base case
    dp[0] = 0;

    for(var i = 0; i < dp.Length; i++)
    {
        foreach (var coin in coins)
        {
            if(i-coin<0) continue;

            if (1 + dp[i - coin] < dp[i]) dp[i] = 1 + dp[i - coin];
        }
    }

    if (dp[amount] == amount + 1) return -1;
    return dp[amount];
}