零钱问题

2020-11-17 本文已影响0人锦绣拾年

部分参考labuladong 阅读笔记

动态规划

适用范围：一般是为了求最值。

最值，一般都需要穷举来找到最合适的值。

问题特征：有重叠子问题，具备最优子结构。因此可以通过备忘录的方式减少重复穷举。

一般需要列出状态转移方程。【可以当做是一种穷举方法】

零钱问题1

给定不同面额的硬币 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] <= 231 - 1
0 <= amount <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

执行用时：1440 ms, 在所有 Python3 提交中击败了73.10%的用户

内存消耗：16.2 MB, 在所有 Python3 提交中击败了17.03%的用户

题目解析

因为看笔记知道需要用动态规划法。但写出来还是用了很久。

其中：我开始没有循环coins中每一个，只取最大的（因为想，既然最少那每次选最大就可）。但是忽略了 11 （5,2,1） ——》用了【5,5,1】没有用2。

假设我们知道 F(S)，即组成金额 S 最少的硬币数，最后一枚硬币的面值是 C。那么由于问题的最优子结构，转移方程应为：

但我们不知道最后一枚硬币的面值是多少，所以我们需要枚举每个硬币面额值

$c_0,c_1,\dots,c_{n-1}$ 并选择其中的最小值。下列递推关系成立：

$F(S) = min_{i=0\dots n-1}F(S-c_i)+1 subject \quad to \quad S-c_i\ge0$

动态规划方程

1604747121(1).png

为了避免重复的计算，我们将每个子问题的答案存在一个数组中进行记忆化，如果下次还要计算这个问题的值直接从数组中取出返回即可，这样能保证每个子问题最多只被计算一次。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# import sys
# sys.setrecursionlimit(100000)
class Solution:
    
    def getchange(self, coins: List[int], amount: int,beiwang) -> int:
        # if amount< 0:
        #     return -1
        if amount ==0:
            return 0
        res = 20000
        for index in coins:
            if index <= amount:
                new_am = amount -index;
                if beiwang[new_am] == -1:
                    continue
                elif beiwang[new_am] >0:
                    res = min(beiwang[new_am],res)
                else:
                    new_res = self.getchange(coins,amount-index,beiwang)
                    beiwang[new_am]=new_res
                    if new_res!=-1:
                        res = min(new_res,res)
        if res == 20000:
            return -1
        else:
            return res+1
                    

    
    def coinChange(self, coins: List[int], amount: int) -> int:
        

        # coins.sort()
        b = []
        for i in range(10000):
            b.append(-2)
        res=self.getchange(coins,amount,b)
        return res

标准解法：

注意的地方：

用字典，不需要用列表标注。
注意这里在方法里写方法。
不需要 coin<amount 直接用<0就可。
执行用时：1880 ms, 在所有 Python3 提交中击败了24.92%的用户

内存消耗：42.6 MB, 在所有 Python3 提交中击败了6.47%的用户

# import sys
# sys.setrecursionlimit(100000)
class Solution:

    def coinChange(self, coins: List[int], amount: int) -> int:
        memo = dict()

        def dp(n):
            # 查备忘录，避免重复计算
            if n in memo: return memo[n]  #
            if n == 0: return 0
            if n < 0: return -1
            res = float('INF')
            for coin in coins:
                subproblem = dp(n - coin)
                if subproblem == -1:
                # if subproblem == -1:
                    continue
                res = min(res, 1 + subproblem)
            # 记⼊备忘录
            memo[n] = res if res != float('INF') else -1
            return memo[n]
        return dp(amount)

时间复杂度

时间复杂度：O(Sn)，其中 S 是金额，n 是面额数。我们一共需要计算 S 个状态的答案，且每个状态 F(S) 由于上面的记忆化的措施只计算了一次，而计算一个状态的答案需要枚举 n个面额值，所以一共需要 O(Sn)的时间复杂度。
空间复杂度：O(S)，我们需要额外开一个长为 S 的数组来存储计算出来的答案 F(S)

上面的解法是由大额数值到小额数值，也可以反过来，由小额值到大额值。

1605448906(1).png

直接一一计算每一个值的由来。

1605448976(1).png

(根据解法理解，应该外层是钱数循环，内层是coin循环，在LeetCode解法中，Java和C++都是这样写的，只有Python把coin循环放在外面。) 原因应该是Python循环遍历的特殊性可以减少比较次数。

coin放在外面：表明先算，货币1、[1/2]组成各个amount的值。
amount放在外面，表明算1/2/3 amount 由货币1,2,5 组成的值。
执行用时：1156 ms, 在所有 Python3 提交中击败了89.95%的用户

内存消耗：13.4 MB, 在所有 Python3 提交中击败了81.65%的用户

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1 

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

coin放在里面：

执行用时：1356 ms, 在所有 Python3 提交中击败了80.11%的用户

内存消耗：13.5 MB, 在所有 Python3 提交中击败了55.30%的用户

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for x in range(1, amount + 1):
            # print(x)
            for coin in coins:
                if coin <= x :
                    dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

剪枝解法

还有一种dfs+剪枝解法，其实符合我的开始的思路：（剪枝可以大幅度减少不必要的计算）

https://leetcode-cn.com/problems/coin-change/comments/93657

执行用时：160 ms, 在所有 Python3 提交中击败了98.70%的用户

内存消耗：13.4 MB, 在所有 Python3 提交中击败了77.83%的用户

注意事项

Python除法，由于没有限定类型，所以默认是float。

class Solution:
    mincount = int(sys.maxsize) #int最大值
    def findchange(self,index,coins,amount,count):
        # print(self.mincount)
        tmpres = int(amount/coins[index])
        if index < 0 or count+tmpres >= self.mincount: #已经超过
            # print("-=-=")
            return;
        if(amount%coins[index]==0):
            self.mincount = min(self.mincount,count+tmpres)
            return
        i = tmpres
        while i>=0:
            self.findchange(index-1,coins,amount-i*coins[index],count+i)#算是从大开始,遍历所有情况
            i-=1
                
    
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort()#从大到小排序
        # print(coins)
        self.findchange(len(coins)-1,coins,amount,0)
        return self.mincount if self.mincount != sys.maxsize else -1

零钱问题2

题目

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

 

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:

输入: amount = 10, coins = [10] 
输出: 1
 

注意:

你可以假设：

0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change-2
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

python 二维数组初始化

 dp = [[0] * (amount + 1) for _ in range(len(coins) + 1)] amount =5 len(coins)=3
 
[[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]

超时

class Solution(object):
    count = 0
    def foundcount(self,amount,coins,index):
        while index>=0 and amount<coins[index] :
            index = index-1
        if index <0 and amount!=0:
            return
        if amount==0:
            self.count+=1
            return
        if amount<0:
            return

        for i in range(int(amount/coins[index]+1)):
            t = i*coins[index]
            self.foundcount(amount-t,coins,index-1)
      

    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        self.foundcount(amount,coins,len(coins)-1)
        return self.count

递推公式一步步计算（但是肯定多计算很多，时间换空间）

执行用时：3564 ms, 在所有 Python3 提交中击败了5.02%的用户

内存消耗：98.2 MB, 在所有 Python3 提交中击败了5.03%的用户

class Solution(object):
    count = 0
    def foundcount(self,amount,coins,tmp):
        for i in range(1,len(coins)):
            for j  in range(1,amount+1):
                tmp[i][j]=0
                for t in range(0,int(j/coins[i])+1): 
                    tmp[i][j]+=tmp[i-1][j-t*coins[i]] #等于不用新货币时之前货币区间的加和
                    # print(i,j,tmp[i][j])

    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        coins.sort()
        if len(coins)==0:
            if amount==0:
                return 1
            else:
                return 0
        tmp = [{0:1}for i in range(len(coins))]# 所有的0都是一种结果

        for i in range(amount+1):
            if i%coins[0]==0:
                tmp[0][i]=1
            else:
                tmp[0][i]=0
        self.foundcount(amount,coins,tmp)
        # print(tmp)
        return tmp[len(coins)-1][amount]

官方题解：

执行用时：128 ms, 在所有 Python3 提交中击败了98.99%的用户

内存消耗：13.5 MB, 在所有 Python3 提交中击败了56.80%的用户

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] += dp[x - coin]
        return dp[amount]

作者：LeetCode
链接：https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1,vector<int> (amount + 1));
        
        dp[0][0] = 1; // 有一种方案凑成 0 元，那就是 一个也不选
        
        for(int i = 1;i <= n; i++)
            for(int j = 0; j <= amount; j++)
            {
                dp[i][j] = dp[i - 1][j];//只用之前的区间组成
                if(coins[i - 1] <= j)//用了新的区间数字，至少也用了一个，所以就等于之前的。
                     dp[i][j] += dp[i][j - coins[i - 1]] ;  //我觉得这个地方好难想
            }
               
        return dp[n][amount];
    }
};

https://leetcode-cn.com/problems/coin-change-2/comments/424488