# Leetcode 322 Coin Change DP(Leetcode 322 Coin Change DP)-其他

## Leetcode 322 Coin Change DP(Leetcode 322 Coin Change DP)

You are given an integer array representing coins of different denominations and an integer representing a total amount of money.

``coins``
``amount``

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return .

``-1``

You may assume that you have an infinite number of each kind of coin.

### Solution

``````class Solution {
private:
int dp[10004];

public:
int coinChange(vector<int>& coins, int amount) {
if(amount==0)return 0;
int n = coins.size();
int MAX = 9999999;
for(int i=0;i<=amount;i++)dp[i] = MAX;
for(int j=0;j<n;j++){
if(amount>=coins[j])dp[coins[j]]=1;
}

for(int i=1;i<=amount;i++){
for(int j=0;j<n;j++){
if(coins[j]<=i){
dp[i] = min(dp[i], 1 + dp[i-coins[j]] );
}
}
}
if(dp[amount]>amount)return -1;
else return dp[amount];
}
};
``````
————————

You are given an integer array representing coins of different denominations and an integer representing a total amount of money.

``coins``
``amount``

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return .

``-1``

You may assume that you have an infinite number of each kind of coin.

### Solution

Let \ (DP [i] \) represent the minimum number of components of \ (amount = I \). In case of transfer, it is obvious to enumerate every coin less than \ (amount \):

``````class Solution {
private:
int dp[10004];

public:
int coinChange(vector<int>& coins, int amount) {
if(amount==0)return 0;
int n = coins.size();
int MAX = 9999999;
for(int i=0;i<=amount;i++)dp[i] = MAX;
for(int j=0;j<n;j++){
if(amount>=coins[j])dp[coins[j]]=1;
}

for(int i=1;i<=amount;i++){
for(int j=0;j<n;j++){
if(coins[j]<=i){
dp[i] = min(dp[i], 1 + dp[i-coins[j]] );
}
}
}
if(dp[amount]>amount)return -1;
else return dp[amount];
}
};
``````