class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0)
return 0;
vector<int> dp;
int max = amount;
for (int i = 0; i < coins.size(); i++)
{
if (coins[i] > max && coins[i] != INT_MAX)
{
max = coins[i];
}
}
dp.resize(max + 1, -1);
for (int i = 0; i < coins.size(); i++)
{
if (coins[i] < dp.size())
dp[coins[i]] = 1;
}
for (int i = 1; i <= amount; i++)
{
int mi = INT_MAX;
for (int j = 0; j < coins.size(); j++)
{
if (i > coins[j] && dp[i - coins[j]] != -1)
{
int num = min(dp[i - coins[j]] + 1, dp[i]!=-1? dp[i]:INT_MAX);
if (mi > num)
{
mi = num;
}
}
}
if (mi != INT_MAX)
{
dp[i] = min(dp[i] != -1 ? dp[i] : INT_MAX, mi);
}
}
return dp[amount];
}
};
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0)
return 0;
vector<int> dp;
int max = amount;
for (int i = 0; i < coins.size(); i++)
{
if (coins[i] > max && coins[i] != INT_MAX)
{
max = coins[i];
}
}
dp.resize(max + 1, -1);
for (int i = 0; i < coins.size(); i++)
{
if (coins[i] < dp.size())
dp[coins[i]] = 1;
}
for (int i = 1; i <= amount; i++)
{
int mi = INT_MAX;
for (int j = 0; j < coins.size(); j++)
{
if (i > coins[j] && dp[i - coins[j]] != -1)
{
int num = min(dp[i - coins[j]] + 1, dp[i]!=-1? dp[i]:INT_MAX);
if (mi > num)
{
mi = num;
}
}
}
if (mi != INT_MAX)
{
dp[i] = min(dp[i] != -1 ? dp[i] : INT_MAX, mi);
}
}
return dp[amount];
}
};
评论
发表评论