322. Coin Change

Q:

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

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.

 

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

 

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

A:
就是DP，每次计算以前的。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> vec(amount+1,-1);
        vec[0] = 0;
        for(int val =1; val<= amount; ++val){
            for(int c : coins){
                int preVal = val - c;
                if(preVal >= 0 && vec[preVal] >=0 ){
                    vec[val]= vec[val]<0? 1+ vec[preVal] : min(vec[val], 1+vec[preVal]);
                }
            }
        }
        return vec[amount];
    }
};

错误：

忘了检查 之前的位置是不是 -1 了

*********第二遍  没有直接 想出来用DP，  改用递归，然后就SB了

public class Solution {
    public int coinChange(int[] coins, int amount) {
        return helper(coins,0,amount);
    }
    private int helper(int[] coins, int index , int amount){
        if(amount ==0)
            return 0;
        if(index>= coins.length || amount <0)
            return -1;
        int withCurrent = helper(coins,index, amount-coins[index]);
        int withoutCurrent = helper(coins,index+1, amount);
        if(withCurrent == -1 ){
            return withoutCurrent;
        }
        if(withoutCurrent == -1){
            return 1 + withCurrent;
        }
        return Math.min(1+withCurrent, withoutCurrent);
    }
} 

Mistakes:

如果Array.fill了 -1 ，  则 不能直接用 min() 函数的
如果Array.fill 了MAX_VALUE，则最后结果的时候，需要检测一下