dp、贪心、dfs

题目

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

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

示例1：

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

示例2：

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

示例3：

输入：coins = [1], amount = 0
输出：0

示例4：

输入：coins = [1], amount = 1
输出：1

示例5：

输入：coins = [1], amount = 2
输出：2

提示：$1 <= coins.length <= 12\
1 <= coins[i] <= 2^{31}- 1\
0 <= amount <= 10^4$

题解

方法一:二维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def coinChange(self, coins, amount) -> int:
        if amount < 0:
            return - 1
        dp = [[amount + 1 for _ in range(len(coins) + 1)]
              for _ in range(amount + 1)]
        # 初始化第一行为0，其他为最大值（也就是amount + 1）

        for j in range(len(coins) + 1):
            dp[0][j] = 0

        for i in range(1, amount + 1):
            for j in range(1, len(coins) + 1):
                if i - coins[j - 1] >= 0:
                    dp[i][j] = min(
                        dp[i][j - 1], dp[i - coins[j - 1]][j] + 1)
                else:
                    dp[i][j] = dp[i][j - 1]

        return -1 if dp[-1][-1] == amount + 1 else dp[-1][-1]
1
2
3
4
5
a=Solution()
coins = [1, 2, 5]
amount = 11
result =a.coinChange(coins,amount)
print(result)
3

复杂度分析

  • 时间复杂度：O(amonut∗len(coins))
  • 空间复杂度：O(amount * len(coins))

dp[i][j] 依赖于dp[i][j - 1]和 dp[i - coins[j - 1]][j] + 1)这是一个优化的信号，我们可以将其优化到一维,具体见下方。

方法二：一维数组

自上而下（动态规划）

转移方程：

  • F(S)表示组成金额S的最少硬币数，最后一枚硬币值为C，则最优子结构为$$F(S)=F(S-C)+1$$

  • 不能确定最后一枚硬币，故枚举每个硬币值$c_0,c_1,c_2,\cdots,c_{n-1}$，选择最小值。递推关系如下：
    $$F(S)=min_{i=0,..,n-1}{F(S-c_i)+1}，S-c_i\geq0 \
    F(S)=0,S=0\
    F(S)=-1,n=0
    $$

自下而上（动态规划）

思路分析

  • 动态规划
  • 子问题

用 dp[i] 来表示组成 i 块钱，需要最少的硬币数，那么

  1. 第 j 个硬币我可以选择不拿 这个时候， 硬币数 = dp[i]
  2. 第 j 个硬币我可以选择拿 这个时候， 硬币数 = dp[i - coins[j]] + 1
  3. 和背包问题不同， 硬币是可以拿任意个
  4. 对于每一个 dp[i] 我们都选择遍历一遍 coin， 不断更新 dp[i]

状态转移方程

仍定义 F(i) 为组成金额 i 所需最少的硬币数量，假设在计算 F(i) 之前，我们已经计算出 F(0)-F(i-1) 的答案。 则 F(i) 对应的转移方程应为
$$F(i)=min_{j=0…n}F(i-c_j)+1$$

示例

coins = [1, 2, 3], amount = 6

在上图可看到：
$F(3)=min((F(3-c_1),F(3,c_2),F(3-c_3))+1$

$=min(F(3-1),F(3-2),F(3-3))+1$

$=min(F(2),F(1),F(0))+1$

$=min(1,1,0)+1$

$=1$

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def coinChange(self, coins, amount) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        
        for i in range(1, amount + 1):
            for j in range(len(coins)):

                if i >= coins[j]:
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1)

        return -1 if dp[-1] == amount + 1 else dp[-1]
1
2
3
4
5
a=Solution()
coins = [1, 2, 5]
amount = 11
result =a.coinChange(coins,amount)
print(result)
3

复杂度

时间复杂度：O(amonut * len(coins))

空间复杂度：O(amount)

方法三：贪心 + dfs

思路分析

  • 贪心
  1. 想要总硬币数最少，肯定是优先用大面值硬币，所以对 coins 按从大到小排序
  2. 先丢大硬币，再丢会超过总额时，就可以递归下一层丢的是稍小面值的硬币
  • 乘法对加法的加速

  1. 优先丢大硬币进去尝试，也没必要一个一个丢，可以用乘法算一下最多能丢几个

    k = amount / coins[c_index] 计算最大能投几个
amount - k * coins[c_index] 减去扔了 k 个硬币
count + k 加 k 个硬币

  2. 如果因为丢多了导致最后无法凑出总额，再回溯减少大硬币数量

  • 最先找到的并不是最优解
  1. 注意不是现实中发行的硬币，面值组合规划合理，会有奇葩情况
  2. 考虑到有 [1,7,10] 这种用例，按照贪心思路 10 + 1 + 1 + 1 + 1 会比 7 + 7 更早找到
  3. 所以还是需要把所有情况都递归完
  • ans 疯狂剪枝
  1. 贪心虽然得不到最优解，但也不是没用的
  2. 我们快速算出一个贪心的 ans 之后，虽然还会有奇葩情况，但是绝大部分普通情况就可以疯狂剪枝了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution():
    def coinChange(self, coins, amount):
        def coinChanging(coins, amount, c_index, count, ans):
            if amount == 0:
                return min(ans, count)
            if c_index == len(coins):
                return ans
            k = amount // coins[c_index]
            while k >= 0 and k + count < ans:
                ans = coinChanging(coins, amount - k * coins[c_index], c_index + 1, count + k, ans)
                k -= 1
            return ans
        if amount == 0:
            return 0
        coins.sort(reverse=True)
        ans = coinChanging(coins, amount, 0, 0, float('inf'))
        return ans if ans != float('inf') else -1
1
2
3
4
5
a=Solution()
coins = [1, 2, 5]
amount = 11
result =a.coinChange(coins,amount)
print(result)
3

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://fishni.github.io/2020/12/22/LeetCode-C-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-322.%20%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2/