class Solution {

     Map<Integer, Integer> hashMap = new HashMap<>();

     public int coinChange(int[] coins, int amount) {

         hashMap.put(0, 0);//0元不需要被货币表示

         if(hashMap.containsKey(amount)) return hashMap.get(amount);

         int curMin = amount + 1;//货币的最小面值只能是1，所以最多能被表示成amount个货币，那么amount+1就相当于正无穷

         for(int coin : coins) {

             if(amount >= coin) {

                 int cur = coinChange(coins, amount - coin) + 1;

                 if(cur > 0 && curMin > cur) curMin = cur;//cur==0就意味着amount-coin不能被当前货币表示

             }

         }

         if(curMin == amount + 1) {//已经遍历过的元素的表示数目要及时记录

             hashMap.put(amount, -1);

         }else {

             hashMap.put(amount, curMin);

         }

         return hashMap.get(amount);

     }

 }

 class Solution {

     Map<Integer, Integer> hashMap = new HashMap<>();

     public int coinChange(int[] coins, int amount) {

         hashMap.put(0, 0);//0元不需要被货币表示

         int MAX = amount + 1;

         for(int i = 1; i <= amount; i++) {

             hashMap.put(i, MAX);//面值为i能被表示成货币的数目的最小值

             for(int coin : coins) {

                 if(i >= coin) {

                     hashMap.put(i, Math.min(hashMap.get(i), hashMap.get(i - coin) + 1));

                 }

             }

         }

         //对于面值i，只要i映射的值大于i就相当于i不能被当前的货币表示

         return hashMap.get(amount) > amount ? -1 : hashMap.get(amount);

     }

 }