算法笔记_面试题_8.零钱兑换

迷南。 2023-02-20 13:39 22阅读 0赞

# 题目 #

[322. 零钱兑换][322.]

难度：中等

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

**示例 1:**

输入: coins = [1, 2, 5], amount = 11
    输出: 3
    解释: 11 = 5 + 5 + 1

**示例 2:**

输入: coins = [2], amount = 3
    输出: -1

**说明**:  
你可以认为每种硬币的数量是无限的。

# 解法1-递归 #

思路：与爬楼梯问题类似，比如11块，能分成最小的硬币数\[1,2,5\]。 f(n) = min(f(n-1), f(n-2),f(n-5)) +1 即要到达第n个台阶，可能有三种情况，上一步（子问题）是f(n-1) 或f(n-2)或f(n-5) ，再+1步到达f(n), 此时取三者（上一步）中最小的,再加1即为结果。下面代码中的amount相当于n阶台阶，coin相当于一次可以上升的台阶数。

// ONGING: 超时？未通过(递归重复调用？)

int coinChange(vector<int>& coins, int amount) 
    {
        if (amount < 0) return -1;
        if (amount == 0) return 0;
        int ans = INT_MAX;
        for(int coin : coins)
        {
            if (amount-coin < 0) continue;
            int subProb = coinChange(coins, amount - coin);
            if (subProb == -1) continue;
            ans = min(ans, subProb + 1);
        }
        return ans == INT_MAX ? -1 : ans;
    }

# 解法2-动态规划 #

## 思路： ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70 1][]

## 代码： ##

int coinChange(vector<int>& coins, int amount) {
      int Max = amount + 1;
      vector<int> dp(amount + 1, Max);    //初始化dp数组元素：如11元，最少币数12
      dp[0] = 0;
      for (int i = 1; i <= amount; ++i) {  // i从1开始 dp[i] 表示组成i元需要的最少硬币数
        for (int j = 0; j < (int)coins.size(); ++j) {
          if (coins[j] <= i) {
            dp[i] = min(dp[i], dp[i - coins[j]] + 1); //在j的迭代过程中，选择f(n-1)、f(n-2、f(n-5)最小的(假设coins=[1,2,5])，再加1
          }
        }
      }
      return dp[amount] > amount ? -1 : dp[amount];  //初始化的dp元素没有被修改（如12>11），意味着无解，返回-1
    }

### 复杂度分析 ###

*  时间复杂度：O(Sn)，其中 S 是金额，n 是面额数。我们一共需要计算 O(S) 个状态，S 为题目所给的总金额。对于每个状态，每次需要枚举 n 个面额来转移状态，所以一共需要 O(Sn) 的时间复杂度。
 *  空间复杂度：O(S)。DP 数组需要开长度为总金额 S 的空间。

[322.]: https://leetcode-cn.com/problems/coin-change/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200712220928476.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200712220954535.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ==,size_16,color_FFFFFF,t_70