动态规划 LC 零钱兑换问题

阅读量：

问题

在这里插入图片描述

暴力法实现与分析

通过采用深度优先搜索或广度优先搜索的方式，对所有可能的零钱组合进行遍历，当遍历得到的和超过指定金额时，即终止当前遍历过程，从而寻找到能够恰好等于金额的最短组合路径。在未进行剪枝优化的情况下，该方法可能会导致运行超时，以下展示的是深度优先搜索的具体实现方式。

复制代码

    int minRs = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        if(amount == 0)
            return 0;
        quickSort(coins,0,coins.length-1);
        Stack<Integer> stack = new Stack<>();
        for(int coin : coins){
            stack.push(coin);
            int rs = dfs(coins,amount,stack,coin);

全部评论 (0)

还没有任何评论哟~