题解 | #换钱的最少货币数#| JAVA| DFS | BFS | 动态规划 |

懒。

动态规划

  public int minMoney (int[] arr, int aim) {
// 初始化
        table = new int[aim+1];
        return dp(arr,aim);
    }
    // 进行剪枝 ， 一般动态规划都要
    int[] table ;
     /**
     * 定义 ， 要凑出金额 amount ， 至少需要  dp(amount) 个硬币
     *
     * @param arr
     * @param amount 要凑的金额
     * @return 硬币数量
     */
    public int dp(int[] arr, int amount){
        //base case  基本返回操作， 当金额等于的0 时候就不用返回了。
        if(amount == 0){
            return 0;
        }
        if(amount < 0){
            return -1;
        }
        // 返回某个金额的最少 金币数
        if(table[amount]!=0){
            return table[amount];
        }

        int res = Integer.MAX_VALUE;

        for (int i = 0; i < arr.length; i++) {
             //遍历金币数组，每个可能都尝试
            int subproblem = dp(arr, amount - arr[i]);
            // 无解跳过
            if(subproblem == -1){
                continue;
            }
            res = Math.min(subproblem + 1, res);
        }
        res = res ==  Integer.MAX_VALUE ? -1 : res;
        table[amount] = res;
        return res;
    }

DFS

   public int minMoney(int[] arr, int amount) {
        Arrays.sort(arr);
        dfs(arr, arr.length - 1, 0, amount);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    int res = Integer.MAX_VALUE;

    public void dfs(int[] coins, int index, long count, int amount) {
        //剪枝，  下标小于0 ， 或者 比 res 大的没有必要统计
        if (index < 0 || count + amount / coins[index] >= res)
            return;
        // 计算
        if (amount % coins[index] == 0) {
            res = Math.min(res, (int) count + amount / coins[index]);
            return;
        }
        // 递归
        for (int i = amount / coins[index]; i >= 0; i--) {
            dfs(coins, index - 1, count + i, amount - i * coins[index]);
        }
    }

BFS

   public int minMoney(int[] coins, int amount) {
        int count = 0;
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(amount);
        int[] table = new int[amount + 1];

        while (!deque.isEmpty()) {
            int len = deque.size();
            for (int i = 0; i < len; i++) {
                int temp = deque.pop();
                if (temp == 0) {
                    return count;
                }
                for (int coin : coins) {
                    if (temp >= coin && table[temp - coin] == 0) {
                        deque.add(temp - coin);
                        table[temp - coin] = 1;
                    }
                }
            }
            count += 1;
        }
        return -1;
    }