欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode——322. 零钱兑换

程序员文章站 2022-04-04 09:02:38
...

Leetcode——322. 零钱兑换
思路:动态规划
自顶向下(回溯剪枝):

class Solution
{
public:
    int hash[1000000]={0};
    int re=0;
    void dy(vector<int>& coins,int remain,int num)
    {
        if(hash[remain]==0)
        {
            hash[remain]=num;
            for(int i=coins.size()-1;i>=0;i--)
            {
                if(remain-coins[i]>=0)
                {
                    dy(coins,remain-coins[i],num+1);
                }
            }
        }
        else
        {
            if(hash[remain]<=num)
            {
                return ;
            }
            else
            {
                hash[remain]=num;
                for(int i=coins.size()-1;i>=0;i--)
                {
                    if(remain-coins[i]>=0)
                    {
                        dy(coins,remain-coins[i],num+1);
                    }
                }
            }
        }
        return ;
    }
    int coinChange(vector<int>& coins, int amount)
    {
        if(amount==0)
        {
            return 0;
        }
        dy(coins,amount,0);
        if(hash[0]==0)
        {
            return -1;
        }
        else
        {
            return hash[0];
        }
    }
};

自底向上:


class Solution
{
public:
    int coinChange(vector<int>& coins, int amount)
    {
        vector<int> ve(amount+1,amount+1);
        ve[0]=0;
        for(int i=0;i<=amount;i++)
        {
            for(int j=0;j<coins.size();j++)
            {
                if(i-coins[j]>=0)
                {
                    ve[i]=min(ve[i],ve[i-coins[j]]+1);
                }
                else
                {
                    continue;
                }
            }
        }
        if(ve[amount]==amount+1)
        {
            return -1;
        }
        else
        {
            return ve[amount];
        }
    }
};