K种面值的硬币,面值分别为c1、c2...ck,每种硬币无限,再给一个总金额amount,问最少需要几枚硬币可以凑出金额,不能返回-1.

int coinChange(int[] coins,int amount)

暴力破解

1.确定状态,也就是变量。本题中硬币无限,所以状态只有总金额。

2.dp函数的定义:当前目标金额是n,至少需要dp[n]个硬币

3.确定[选择]并择优,也就是对于每个状态,可以做出什么选择改变当前状态!无论目标金额是多少,选择就是从面额列表中选择一个coin,然后目标金额就会减少。

4.明确base case,显然amount为0时,返回0,当前金额小于0,无解返回-1;


在本题中,当前面额是amount,若已知amount-coin的最优解,那么+1就是当前解,其中coin是硬币面板中的一个!

#伪代码框架
def coinChange(coins:List[int],amount: int)
    def dp(n):
        for coin in coins:
            res=min(res,1+dp(n-coin))
    return res
return dp(amount)

def coinChange(coins: List[int],amount: int):
    def dp(n):
        #base case
        if n==0: return 0;
        if n<0: return -1;
        # initialize
        res=float('INF')
        for coin in coins:
            # sub problem no result, continue
            subproblem=dp(n-coin)
            if subproblem == -1: continue
                res=min(res,1+subproblem)
        return res if res!=float('INF') else -1
return dp(amount)


复杂度:子问题总数*每个子问题时间
本题子问题有一个for循环,因此复杂度为O(kn^k)

带备忘录的递归

def coinChange(coins: List[]int,amount: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: continue
            res=min(res,1+subproblem)
        memo[n]= res if res!=float('INF') else -1
        # write into Memorandum
        return memo[n]
return dp(amount)

简化为:

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

自底向上的递归

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

322.零钱兑换

Last modification:April 19th, 2020 at 11:49 pm