CoinChange.java

package com.learning.leet.problems;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

/**
 * https://leetcode.com/problems/coin-change/
 */
public class CoinChange {

    public static void main(String args[]){
        CoinChange change = new CoinChange();
        HashMap<Integer,Integer> dpCoin = new HashMap<>();
        int value = change.coinChange(new int[]{1,2,5},12, dpCoin);
        System.out.println(value);

    }
    public int coinChange(int[] coins, int amount, HashMap<Integer,Integer> dpMap) {
        if(amount==0)return 0;

        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0; i<coins.length;i++){
            if(amount-coins[i] >= 0){
                int ret = 0;
                if(dpMap.containsKey(amount-coins[i])){
                    ret = dpMap.get(amount-coins[i]);
                }else{
                    ret = coinChange(coins, amount-coins[i], dpMap);
                    dpMap.put(amount-coins[i],ret);
                }
                if(ret!=-1){
                    Integer val = 1+ret;
                    res.add(val);
                }

            }
        }

        return res.size()==0?-1:Collections.min(res);
    }




}