久久精品人,六月百合影院,亚洲中文字幕乱码色色

部分參考labuladong 閱讀筆記

動(dòng)態(tài)規(guī)劃

適用范圍：一般是為了求最值。

最值，一般都需要窮舉來找到最合適的值。

問題特征：有重疊子問題，具備最優(yōu)子結(jié)構(gòu)。因此可以通過備忘錄的方式減少重復(fù)窮舉。

一般需要列出狀態(tài)轉(zhuǎn)移方程?！究梢援?dāng)做是一種窮舉方法】

零錢問題1

給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

你可以認(rèn)為每種硬幣的數(shù)量是無限的。

 

示例 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

執(zhí)行用時(shí)：1440 ms, 在所有 Python3 提交中擊敗了73.10%的用戶

內(nèi)存消耗：16.2 MB, 在所有 Python3 提交中擊敗了17.03%的用戶

題目解析

因?yàn)榭垂P記知道需要用動(dòng)態(tài)規(guī)劃法。但寫出來還是用了很久。

其中：我開始沒有循環(huán)coins中每一個(gè)，只取最大的（因?yàn)橄?，既然最少那每次選最大就可）。但是忽略了 11 （5,2,1） ——》用了【5,5,1】沒有用2。

假設(shè)我們知道 F(S)，即組成金額 S 最少的硬幣數(shù)，最后一枚硬幣的面值是 C。那么由于問題的最優(yōu)子結(jié)構(gòu)，轉(zhuǎn)移方程應(yīng)為：

但我們不知道最后一枚硬幣的面值是多少，所以我們需要枚舉每個(gè)硬幣面額值

$c_0,c_1,\dots,c_{n-1}$ 并選擇其中的最小值。下列遞推關(guān)系成立：

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

動(dòng)態(tài)規(guī)劃方程

1604747121(1).png

為了避免重復(fù)的計(jì)算，我們將每個(gè)子問題的答案存在一個(gè)數(shù)組中進(jìn)行記憶化，如果下次還要計(jì)算這個(gè)問題的值直接從數(shù)組中取出返回即可，這樣能保證每個(gè)子問題最多只被計(jì)算一次。

作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

# 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

標(biāo)準(zhǔn)解法：

注意的地方：

用字典，不需要用列表標(biāo)注。
注意這里在方法里寫方法。
不需要 coin<amount 直接用<0就可。
執(zhí)行用時(shí)：1880 ms, 在所有 Python3 提交中擊敗了24.92%的用戶

內(nèi)存消耗：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):
            # 查備忘錄，避免重復(fù)計(jì)算
            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)

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度：O(Sn)，其中 S 是金額，n 是面額數(shù)。我們一共需要計(jì)算 S 個(gè)狀態(tài)的答案，且每個(gè)狀態(tài) F(S) 由于上面的記憶化的措施只計(jì)算了一次，而計(jì)算一個(gè)狀態(tài)的答案需要枚舉 n個(gè)面額值，所以一共需要 O(Sn)的時(shí)間復(fù)雜度。
空間復(fù)雜度：O(S)，我們需要額外開一個(gè)長為 S 的數(shù)組來存儲(chǔ)計(jì)算出來的答案 F(S)

上面的解法是由大額數(shù)值到小額數(shù)值，也可以反過來，由小額值到大額值。

1605448906(1).png

直接一一計(jì)算每一個(gè)值的由來。

1605448976(1).png

(根據(jù)解法理解，應(yīng)該外層是錢數(shù)循環(huán)，內(nèi)層是coin循環(huán)，在LeetCode解法中，Java和C++都是這樣寫的，只有Python把coin循環(huán)放在外面。) 原因應(yīng)該是Python循環(huán)遍歷的特殊性可以減少比較次數(shù)。

coin放在外面：表明先算，貨幣1、[1/2]組成各個(gè)amount的值。
amount放在外面，表明算1/2/3 amount 由貨幣1,2,5 組成的值。
執(zhí)行用時(shí)：1156 ms, 在所有 Python3 提交中擊敗了89.95%的用戶

內(nèi)存消耗：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）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

coin放在里面：

執(zhí)行用時(shí)：1356 ms, 在所有 Python3 提交中擊敗了80.11%的用戶

內(nèi)存消耗：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+剪枝解法，其實(shí)符合我的開始的思路：（剪枝可以大幅度減少不必要的計(jì)算）

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

執(zhí)行用時(shí)：160 ms, 在所有 Python3 提交中擊敗了98.70%的用戶

內(nèi)存消耗：13.4 MB, 在所有 Python3 提交中擊敗了77.83%的用戶

注意事項(xiàng)

Python除法，由于沒有限定類型，所以默認(rèn)是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: #已經(jīng)超過
            # 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

題目

給定不同面額的硬幣和一個(gè)總金額。寫出函數(shù)來計(jì)算可以湊成總金額的硬幣組合數(shù)。假設(shè)每一種面額的硬幣有無限個(gè)。 

 

示例 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
 

注意:

你可以假設(shè)：

0 <= amount (總金額) <= 5000
1 <= coin (硬幣面額) <= 5000
硬幣種類不超過 500 種
結(jié)果符合 32 位符號(hào)整數(shù)

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/coin-change-2
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法

python 二維數(shù)組初始化

 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]]

超時(shí)

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

遞推公式一步步計(jì)算（但是肯定多計(jì)算很多，時(shí)間換空間）

執(zhí)行用時(shí)：3564 ms, 在所有 Python3 提交中擊敗了5.02%的用戶

內(nèi)存消耗：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]] #等于不用新貨幣時(shí)之前貨幣區(qū)間的加和
                    # 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都是一種結(jié)果

        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]

官方題解：

執(zhí)行用時(shí)：128 ms, 在所有 Python3 提交中擊敗了98.99%的用戶

內(nèi)存消耗：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）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

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 元，那就是 一個(gè)也不選
        
        for(int i = 1;i <= n; i++)
            for(int j = 0; j <= amount; j++)
            {
                dp[i][j] = dp[i - 1][j];//只用之前的區(qū)間組成
                if(coins[i - 1] <= j)//用了新的區(qū)間數(shù)字，至少也用了一個(gè)，所以就等于之前的。
                     dp[i][j] += dp[i][j - coins[i - 1]] ;  //我覺得這個(gè)地方好難想
            }
               
        return dp[n][amount];
    }
};

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

零錢問題

零錢問題

動(dòng)態(tài)規(guī)劃

零錢問題1

題目解析

標(biāo)準(zhǔn)解法：

時(shí)間復(fù)雜度

剪枝解法

零錢問題2

題目

解法

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

零錢問題

動(dòng)態(tài)規(guī)劃

零錢問題1

題目解析

標(biāo)準(zhǔn)解法：

時(shí)間復(fù)雜度

剪枝解法

零錢問題2

題目

解法

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av