Coin Change

Coin Change #322

Description:

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:

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Idea:

The minimum number of coins for a value V can be computed using below recursive formula.

If V == 0, then 0 coins required.
If V > 0
   minCoin(coins[0..m-1], V) = min {1 + minCoins(V-coin[i])} 
                               where i varies from 0 to m-1 
                               and coin[i] <= V

DP, 注意，这个要求min，所以如果没法找钱要返回INT_MAX。DP用-1表示没有记录，不然就表示DP[money].

Solution有bug，如果amount==INT_MAX出问题，暂时不考虑了。

Code:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n=amount+1;

        vector<int> DP(n, -1);

        int result=DFS(coins, amount, DP);
        return result==INT_MAX? -1: result;
    }

    int DFS(vector<int>& coins, int amount, vector<int>& DP){
        if(DP[amount]!=-1) return DP[amount];

        if(amount==0){
            DP[amount]=0;
            return amount;
        }

        int min_change=INT_MAX;

        for(int i=0; i<coins.size(); ++i){
            if(coins[i]<=amount){
                min_change=min(min_change, DFS(coins, amount-coins[i], DP));
            }
        }
        if(min_change==INT_MAX) {
            DP[amount]=INT_MAX;
        }
        else{
            DP[amount] = min_change+1;
        }
        return DP[amount];

    }
};