322. Coin Change

This is a classic dynamic programming problem. If you don't know the problem before, it will be tricky. Let dp[i] be the minimal change for amount i. We should try from 1 to the target amount such that should a coin amount be less or equal to i, dp[i] = min(dp[i], dp[i-coins[j]]+1), i.e. the minimal change for amount i will be the minimal change at i-coins[j] plus 1.

1:  class Solution {  
2:  public:  
3:    int coinChange(vector<int>& coins, int amount) {  
4:      vector<int> dp(amount+1, INT_MAX-1);  
5:      dp[0] = 0;  
6:      for (int i = 1; i <= amount; i++) {  
7:        for (int j = 0; j < coins.size(); j++) {  
8:          if (coins[j] <= i) {  
9:            dp[i] = min(dp[i], dp[i-coins[j]]+1);  
10:          }  
11:        }  
12:      }  
13:      return dp[amount] == INT_MAX-1 ? -1 : dp[amount];  
14:    }  
15:  };