1 public class Main { 2  3     /** 4      * 假设有面值1、5、10、21和25分的硬币，找出63分钱，最少用几枚硬币 5      * 用递归来解决  K 分钱的找零问题： 6      * （1）如果可以用一个硬币找零，这就是最少的 7      * （2）否则，对于每个可能的值i，我们可以独立计算找 i 分钱零钱和 K - i 分钱需要的最少硬币数， 然后选择使两者之和最小的i. 8      * @param coins 硬币面值数组 9      * @param change 需要找的钱10      * @return11      */12     public static int makeChange(int[] coins, int change){13         14         int minCoins = change; //最坏的情况时全部用 1 分 的硬币15         16         for (int i = 0; i < coins.length; i++) {17             if (coins[i] == change) {18                 return 1; /* 存在刚好匹配的硬币 返回 1 */19             }20         }21         22         for(int j = 1; j <= change/2; j++){23             int thisCoins = makeChange(coins, j) +24                     makeChange(coins, change-j);25             26             if (thisCoins < minCoins) {27                 minCoins = thisCoins;28             }29         }30         31         return minCoins;32     }33     /**34      * 35      * @param coins36      * @param differentCoins37      * @param maxChange38      * @param coinsUsed39      * @param lastCoin40      */41     public static void makeChange(int[] coins, int differentCoins, int maxChange, int[] coinsUsed,42             int[] lastCoin){43         coinsUsed[0] = 0;44         lastCoin[0] = 1;45         46         for (int cents = 1; cents <= maxChange; cents++) {47             int minCoins = cents;48             int newCoin = 1;49             50             for (int j = 0; j < differentCoins; j++) {51                 if (coins[j] > cents) {52                     continue;53                 }54                 if (coinsUsed[cents - coins[j]] + 1 < minCoins) {55                     minCoins = coinsUsed[cents-coins[j]] + 1;56                     newCoin = coins[j];57                 }58             }59             60             coinsUsed[cents] = minCoins;61             lastCoin[cents] = newCoin;62         }63     }64     65 }