322. 零钱兑换


322. 零钱兑换

动态规划

    public int coinChange(int[] coins, int amount) {
        // 自底向上的动态规划
        if(coins.length == 0){
            return -1;
        }

        // memo[n]的值: 表示的凑成总金额为n所需的最少的硬币个数
        int[] memo = new int[amount+1];
        // 给memo赋初值,最多的硬币数就是全部使用面值1的硬币进行换
        // amount + 1 是不可能达到的换取数量,于是使用其进行填充
        Arrays.fill(memo,amount+1);
        memo[0] = 0;
        for(int i = 1; i <= amount;i++)&#123;
            for(int j = 0;j < coins.length;j++)&#123;
                if(i - coins[j] >= 0)&#123;
                    // memo[i]有两种实现的方式,
                    // 一种是包含当前的coins[i],那么剩余钱就是 i-coins[i],这种操作要兑换的硬币数是 memo[i-coins[j]] + 1
                    // 另一种就是不包含,要兑换的硬币数是memo[i]
                    memo[i] = Math.min(memo[i],memo[i-coins[j]] + 1);
                &#125;
            &#125;
        &#125;

        return memo[amount] == (amount+1) ? -1 : memo[amount];
    &#125;

//作者:sugar666
//链接:https://leetcode-cn.com/problems/coin-change/solution/javadi-gui-ji-yi-hua-sou-suo-dong-tai-gui-hua-by-s/

记忆法

    int[] memo;
    public int coinChange(int[] coins, int amount) &#123;
        if(coins.length == 0)&#123;
            return -1;
        &#125;
        memo = new int[amount];

        return findWay(coins,amount);
    &#125;
    // memo[n] 表示钱币n可以被换取的最少的硬币数,不能换取就为-1
    // findWay函数的目的是为了找到 amount数量的零钱可以兑换的最少硬币数量,返回其值int
    public int findWay(int[] coins,int amount)&#123;
        if(amount < 0)&#123;
            return -1;
        &#125;
        if(amount == 0)&#123;
            return 0;
        &#125;
        // 记忆化的处理,memo[n]用赋予了值,就不用继续下面的循环
        // 直接的返回memo[n] 的最优值
        if(memo[amount-1] != 0)&#123;
            return memo[amount-1];
        &#125;
        int min = Integer.MAX_VALUE;
        for(int i = 0;i < coins.length;i++)&#123;
            int res = findWay(coins,amount-coins[i]);
            if(res >= 0 && res < min)&#123;
                min = res + 1; // 加1,是为了加上得到res结果的那个步骤中,兑换的一个硬币...
            &#125;
        &#125;
        memo[amount-1] = (min == Integer.MAX_VALUE ? -1 : min);
        return memo[amount-1];
    &#125;

作者:sugar666
链接:https://leetcode-cn.com/problems/coin-change/solution/javadi-gui-ji-yi-hua-sou-suo-dong-tai-gui-hua-by-s/

递归 超时

    int res = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) &#123;
        if(coins.length == 0)&#123;
            return -1;
        &#125;

        findWay(coins,amount,0);

        // 如果没有任何一种硬币组合能组成总金额,返回 -1。
        if(res == Integer.MAX_VALUE)&#123;
            return -1;
        &#125;
        return res;
    &#125;

    public void findWay(int[] coins,int amount,int count)&#123;
        if(amount < 0)&#123;
            return;
        &#125;
        if(amount == 0)&#123;
            res = Math.min(res,count);
        &#125;

        for(int i = 0;i < coins.length;i++)&#123;
            findWay(coins,amount-coins[i],count+1);
        &#125;
    &#125;

作者:sugar666
链接:https://leetcode-cn.com/problems/coin-change/solution/javadi-gui-ji-yi-hua-sou-suo-dong-tai-gui-hua-by-s/

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
206. Reverse Linked List 206. Reverse Linked List
206. Reverse Linked List public ListNode reverseList(ListNode head) &#123; ListNode pre=null; Li
2021-02-25 future
下一篇 
172. 阶乘后的零 172. 阶乘后的零
172. 阶乘后的零 public int trailingZeroes(int n) &#123; int zeroCount = 0; for (int i = 5; i <= n;
2021-02-25 future
  目录