leetcode_322 Coin Change
1481 ワード
class Solution
{
public:
int coinChange(vector<int> &coins, int amount)
{
const int INF = 0x7ffffffe;
// dp,
vector<int> dp(amount + 1, INF);
dp[0] = 0; //
for (int i = 0; i <= amount; i++)
{
for (int j = 0; j < coins.size(); j++)
{
//
if (i + coins[j] <= amount && dp[i + coins[j]] > dp[i] + 1)
dp[i + coins[j]] = dp[i] + 1;
}
}
return dp[amount] == INF ? -1 : dp[amount];
}
};
public int coinChange(int[] coins, int amount){
int[] dp = new int[amount + 1];
final int INF = 0x7ffffffe;
// dp[i] , 1
for (int i = 0; i <= amount; i++)
dp[i] = INF;
dp[0] = 1;
//
for(int i = 0; i <= amount; i++){
for (int j = 0; j < coins.length; j++){
if (i + coins[j] <= amount)
dp[i + coins[j]] = Math.min(dp[i + coins[j]], dp[i] + 1);
}
}
return dp[amount] == INF ? -1 : dp[amount];
}