[Leetcode][第322题][JAVA][零钱兑换][回溯][记忆化搜索][动态规划]

谁践踏了优雅 2022-12-01 15:57 164阅读 0赞

#### 【问题描述】\[中等\] ####

#### 【解答思路】 ####

###### 1. 递归（超时） ######

class Solution { 
        int res = Integer.MAX_VALUE;
        public int coinChange(int[] coins, int amount) { 
            if(coins.length == 0){ 
                return -1;
            }
    
            findWay(coins,amount,0);
    
            // 如果没有任何一种硬币组合能组成总金额，返回 -1。
            if(res == Integer.MAX_VALUE){ 
                return -1;
            }
            return res;
        }
    
        public void findWay(int[] coins,int amount,int count){ 
            if(amount < 0){ 
                return;
            }
            if(amount == 0){ 
                res = Math.min(res,count);
            }
    
            for(int i = 0;i < coins.length;i++){ 
                findWay(coins,amount-coins[i],count+1);
            }
        }
    }

###### 2. 记忆化搜索 自上而下 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]  
可以看出在进行递归的时候，有很多重复的节点要进行操作，这样会浪费很多的时间。  
使用数组 memo\[ \] 来保存节点的值  
memo\[n\]表示钱币 n+1可以被换取的最少的硬币数，不能换取就为 -1  
findWay 函数的目的是为了找到 amount 数量的零钱可以兑换的最少硬币数量，返回其值 int

在进行递归的时候，memo\[n\]被复制了，就不用继续递归了，可以直接的调用

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

###### 3. 动态规划 自下而上 ######

![在这里插入图片描述][20200828120204652.png_pic_center]

**时间复杂度：O(N^2) 空间复杂度：O(N)**

class Solution { 
        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++){ 
                for(int j = 0;j < coins.length;j++){ 
                    if(i - coins[j] >= 0){ 
                        // 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);
                    }
                }
            }
    
            return memo[amount] == (amount+1) ? -1 : memo[amount];
        }
    }

#### 【总结】 ####

###### 1. 思路总结 ######

**回溯法-〉递归树-〉重复子问题-〉备忘录/动态规划**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

###### 2.[【数据结构与算法】【算法思想】【联系与区别】回溯 贪心 动态规划 分治][_ _] ######

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d592b93366674ca5aa1836141f95f88b.png
[20200828120204652.png_pic_center]: /images/20221123/ba0b79d4393444fcb294a8fcee721b43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/6ed286b91b2f4e4f864c39cd9c0a643c.png
[_ _]: https://blog.csdn.net/dadongwudi/article/details/108269570