Leetcode——322. 零钱兑换
程序员文章站
2022-04-04 09:02:38
...
思路:动态规划
自顶向下(回溯剪枝):
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];
}
}
};