322. Coin Change

   

QuestionEditorial Solution

Total Accepted: 20289 Total Submissions: 81565 Difficulty: Medium

 

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

Example 1:

coins = [1, 2, 5], amount = 11

return 3 (11 = 5 + 5 + 1)

Example 2:

coins = [2], amount = 3

return -1.

Note:

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

Credits:

Special thanks to  for adding this problem and creating all test cases.

 

 to see which companies asked this question

Hide Tags

 

 

 

转一发题解：

 

给定几个固定面值的硬币，可以无限使用。一个目标数，要求用最少的硬币兑换这个target。

    换一种思路理解题目，每次可以走给定面值的步数，问最少走多少步能达到目标。如此一来便可以用BFS求解。

    第二种解法是DP，dp[i] = min {dp[i - a], dp[i - b], dp[i - c] ...... }。动态规划只要有公式就能很快求解。

    我用DP求解的AC代码

 

 

180 / 180 test cases passed.	Status:  Accepted
Runtime: 76 ms

 

1 #define inf 0x3fffffff 2 #define N 1000005 3  4 int dp[N]; 5 int len; 6  7 class Solution { 8 public: 9     int coinChange(vector
      
       & coins, int amount) {10         len = coins.size();11         sort(coins.begin(),coins.end());12         int i,j;13         //fill(dp,dp + N,inf);14         for(i = 0;i <= amount;i++){15             dp[i] = inf;16         }17         dp[0] = 0;18         19         for(i = 0;i < len;i++){20             for(j = 0;j < amount;j++){21                 if(dp[j] == inf) continue;22                 dp[j + coins[i] ] = min(dp[j + coins[i] ],dp[j] + 1);23             }24         }25         if(dp[amount] == inf) return -1;26         return dp[amount];27     }28 };