[数据结构与算法]322. 零钱兑换 动态规划 | 零钱 | 暴力递归 | 自顶向下

力扣打卡：322. 零钱兑换

解题思路

动态规划的问题，最重要的写出暴力递归的方法

• 暴力递归没有记录结果的数组
• 递归的写法是：定义一个函数，这个函数就可以的结果，不要去想能不能得到结果
• 定义的函数就可以得到结果，然后用子问题的结果结合当前的操作去解决总的问题
• 最后返回需要的结果
• 最重要的是转移方程，也就是怎么连接子问题和当前所在的操作对象

代码

class Solution {
    
    // 想要凑出给定的一个n是否有解，那么暴力的递归解法
    // 对于当前的 amount 去尝试减去coins的任意一个元素，得到的新的amount，
    // 再次去减coins的每一次元素得到的每一个新的amount，重复计算

    // 分析的具体流程：
    // 1. 最基本的情况，如果amount每次减，肯定会有小于0，或者等于0的情况
    // 2. 如果amount等于0，那么需要0种货币
    // 3. 如果amount小于0，那么给出的coins是无解的，返回1
    // 4. 当前的amount去减coins中的任何一个元素，那么肯定存在一个最小的cnt，每次去比较即可
    // 5. 对于当前的计算中，子问题的解，应该需要加上一个1，因为还需要加上当前的面值

    public int coinChange(int[] coins, int amount) {
        // return planA(coins, amount);
        int[] memo = new int[amount+1];
        Arrays.fill(memo, -1000);
        return planB(memo, coins, amount);
    }

    // 暴力递归解法，不熟悉动态规划，先将暴力递归写出来，
    // 如果不熟悉动规而直接写复杂的自顶向下，自底向上，可能会出现参数随便定义，不知如何定义的情况
    public int planA(int[] coins, int amount){
        if(amount<0) return -1; // 定义无解的情况
        if(amount==0) return 0; // 定义基本的情况，当amount等于0时，返回的是0
        int res = Integer.MAX_VALUE; // 定义每次最大的res为整数最大值
        for(int x: coins){
            int subRes = planA(coins, amount-x); // 通过函数的定义，函数定义就是它可以得到一个最小值，不用管具体的实现，写着写着就出来了
            if(subRes == -1) continue; // 如果子问题没有解决的方案，那么直接跳过
            res = Math.min(res, subRes+1); // 子问题有解，那么子问题应该加上当前的面值的一次
        }
        return res==Integer.MAX_VALUE ? -1 : res; // 判断是否全部为无解的情况，如果全部无解，那么res还是整数最大值
    }

    // 自顶向下的分析
    // 先写出暴力解法 （写出了递归就成功了一半，加上一个备忘录，就完全成功了）
    // 每一次计算的结果分析出来就可以了，存起来，运算之前先判断是否已经计算过了，
    // 那么此时在暴力递归的基础上，还需要传递amount的最小是否已经计算过了
    // 用一个备忘录记录起来，因为从0-amount最多就是amount+1个数据，所以定义的数组长度就是amount+1 重点
    // 相比起暴力递归的解法，最多增加了几步，就是记录事情，记录计算过程，最重要的还是在不考虑任何的情况下，写出暴力递归
    public int planB(int[] memo, int[] coins, int amount){
        if(amount<0) return -1;
        if(amount==0) return 0;
        if(memo[amount] != -1000) return memo[amount]; // 初始化的memo的值，不能是题目中有效的数据，这样方便判断是否已经计算过

        int res  = Integer.MAX_VALUE;
        for(int x: coins){
            int subRes = planB(memo, coins, amount-x);
            if(subRes==-1) continue; // 遇到了无解的问题，直接跳过即可，因为如果去计算，此时subRes+1就为0，此时的结果就是0，但实际是-1，无解的结果
            res = Math.min(res, subRes+1);
        }
        res = res== Integer.MAX_VALUE ? -1 : res; // 判断是否全部无解的情况，每次都要记住特殊的判断，如果定义的变量没有改变会怎么样
        memo[amount] = res; // 记录此时amount的res（min），注意加入的位置：在当前的所有计算中都已经完成，能够确定唯一的答案了，那么加入
        return memo[amount];
    }

}