零钱兑换问题--探索动态规划的基本思想

0x01.问题

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

输入示例：1 2 5 11

输出示例：3 

函数形式为： int coinChange1(int* coins, int coinsSize, int amount)

0x02.分析问题

 这个问题的子问题仍然是一定金额所需的硬币最小数，不过金额会越来越少，这些子问题之间相互独立，可以看出，这是一个动态规划问题。

我们需要根据金额的大小来计算其所需的最小硬币，可以根据金额的大小来动态计算，也就是以金额为动态规划的状态。

我们可以先思考一下最简单粗暴的暴力递归方法，例如，我们要计算11，那么我们可以先从硬币中取一枚，等于占用了一枚 ，例如取出1，然后就只需要计算金额为10的最小硬币数，当金额为0时，就是0，当金额小于0时，这种方法行不通，计为-1。

有了这个思路，我们可以得到第一种暴力递归的方法。

0x03.解决办法1--暴力递归

int coinChange(int* coins, int coinsSize, int amount) {
    if (amount < 0)
        return -1;
    if (amount == 0)
        return 0;
    int min = 65535;
    int temp;
    for (int i = 0; i < coinsSize; i++)
    {
        temp = coinChange1(coins, coinsSize, amount - coins[i]);
        if (temp == -1)
            continue;
        min = min < (temp + 1) ? min : (temp + 1);
    }
    if (min != 65535)
    {
        return min;
    }
    else
    {
        return -1;
    }
}

的确可以通过测试用例，但时间复杂度实在是太高了，肯定AC不了这个问题。

仔细一想，时间复杂度达到了恐怖的指数级，这个当然不得行。

我们再次思考一下，时间复杂度那么高得原因是啥，重复调用呗，在上篇博客也提到过，不清楚得话可以画一下递归树，会发现存在大量得递归调用。

那么相应得，我们得解决思路也出来了，就是借用一个标志变量，去记录已经计算出的值。

0x04.解决办法2--记忆化搜索

int coinChange(int* coins, int coinsSize, int amount) {
    if (amount < 0)
        return -1;
    if (amount == 0)
        return 0;
    int* flag = (int*)calloc(amount+1, sizeof(int));
    return checker(flag, amount, coins, coinsSize);
}

int checker(int* flag, int amount,int *coins,int coinsSize)
{
    if (amount == 0)
        return 0;
    if (amount < 0)
        return -1;
    if (flag[amount])
        return flag[amount];
    int min = 65535;//初始化为一个比较大的值
    for (int i = 0; i < coinsSize; i++)
    {
        int temp = checker(flag,amount - coins[i],coins,coinsSize);
        if (temp == -1)
            continue;
        min = min < (temp + 1) ? min : (temp + 1);
    }
    if (min != 65535)
    {
        flag[amount] = min;
        return min;
    }
    else
    {
        flag[amount] = -1;
        return -1;
    }
}

这样时间复杂度就降下来了，设长度是S，硬币的种数是n，那么时间复杂度是 O（S*n），空间复杂度为 O（S）。

这其实也可以看作是自上而下的动态规划。

0x05.解决办法3--动态规划（自下而上）

我们首先需要找一下初始条件，很明显，就是 dp[0]=0。

由于在迭代的过程中需要不断的寻找最小值，所有可以把dp里面的值都初始化为一个较大的值，比如amount+1，是无法达到的。

然后就是自下而上的迭代条件了：

DP[I]=min{DP[i]，DP[i-coin]+1}，DP[i]表示金额为 i 需要的最少硬币数。

下面来看一下C++代码：

int coinChange(vector<int>& coins, int amount)
{
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 0; i < dp.size(); i++)
    {
        for (int coin : coins)
        {
            if (i < coin) continue;
            dp[i] = min(dp[i], dp[i - coin] + 1);
        }
    }
    return (dp[amount] != amount + 1) ? dp[amount] : -1;
}

C代码：

int coinChange(int* coins, int coinsSize, int amount) {
    int* dp = (int*)calloc(amount + 1, sizeof(int));
    int i, j;
    for (i = 0; i <= amount; i++)
    {
        dp[i] = amount + 1;
    }
    dp[0] = 0;
    for (i = 0; i <= amount; i++)
    {
        for (j = 0; j < coinsSize; j++)
        {
            if (i < coins[j]) continue;
            dp[i] = dp[i] < dp[i - coins[j]] + 1 ? dp[i] : dp[i - coins[j]] + 1;
        }
    }
    return (dp[amount] != amount + 1) ? dp[amount] : -1;
}

0x06.探索动态规划的基本思想

什么问题可以用动态规划解决？

• 存在最优子结构，子问题相互独立。
• 遇到找不到最优子结构时，可以适当变换问题思路再来寻找。
• 巧妙的抓住，最值 这个关键字。

解决动态规划问题可尝试的基本思路？

• 如果一下子无法找到动态规划的关键，可以一步一步的去尝试。
• 可以先用最简单的思路写出暴力递归的方法。
• 然后用标志变量，记忆化搜索。
• 最后，找到合适的动态规划思路。

动态规划的基本步骤？

1. 找准状态，简单来说，就是 DP[i] 的含义，你赋予它什么含义，就是什么含义。
2. 找到状态转移方程，也就是迭代表达式，通常可以用具体的数据去打开你的思维。
3. 找到基准条件，也就是初始条件，自下而上的一般是前几个值，自上而下的一般是后几个值。
4. 使用合适的循环条件，将这一思想用代码呈现出来。

动态规划的dp遍历方向？

• 一般来说两种都可以，也可以斜向遍历。
• 具体看哪种方向，基准条件好找。
• 你需要保证在你遍历时，你所用到之前的条件已经被正确计算。
• 你需要保证你遍历的末尾，就是你所需要的答案。

你还可以继续阅读：零钱兑换II--动态规划思路解决相似问题

如果本文对你有帮助，请分享给你的朋友吧！

ATFWUS  --Writing  By 2020--03--14