LeetCode 322：零钱兑换

题目：

思路：

动态规划是求最值，核心是穷举；

动态规划框架：

⾸先，这个问题是动态规划问题，因为它具有 「最优子结构」 的。要符合「最优子结构」，子问题间必须互相独立。

举例：
⽐如说，假设你考试，每⻔科⽬的成绩都是互相独⽴的。你的原问题是考出最⾼的总成绩，那么你的⼦问题就是要把语⽂考到最⾼，数学考到最⾼…… 为了每⻔课考到最⾼，你要把每⻔课相应的选择题分数拿到最⾼，填空题分数拿到最⾼…… 当然，最终就是你每⻔课都是满分，这就是最⾼的总成绩。
得到了正确的结果：最⾼的总成绩就是总分。因为这个过程符合最优⼦结构，「每⻔科⽬考到最⾼」这些⼦问题是互相独⽴，互不干扰的。
如果加⼀个条件：你的语⽂成绩和数学成绩会互相制约，不能同时达到满分，数学分数⾼，语⽂分数就会降低，反之亦然。这样的话，显然你能考到的最⾼总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为「每⻔科⽬考到最⾼」的⼦问题并不独⽴，语⽂数学成绩户互相影响，⽆法同时最优，所以最优⼦结构被破坏。

为什么说它符合最优子结构呢？假设你有⾯值为 1, 2, 5 的硬币，你想求 amount = 11时的最少硬币数（原问题），则 如果你知道凑出 amount = 10, 9, 6 的最少硬币数（子问题），你只需要把子问题的答案加 1 （再选⼀枚面值为 1, 2, 5 的硬币），求个最⼩值，就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独⽴的。

状态转移方程、最优子结构、重叠子问题就是动态规划三要素；
状态转移就是穷举每个状态，再对每个状态的组合求最值；

列出正确的状态转移⽅程？

确定 base case，这个很简单，显然⽬标⾦额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出⽬标⾦额了。
确定「状态」，也就是原问题和子问题中会变化的变量。dp函数的参数或者数组的索引就是状态；
由于硬币数量⽆限，硬币的⾯额也是题⽬给定的，只有⽬标⾦额会不断地向 base case 靠近，所以唯⼀的「状态」就是⽬标⾦额 amount。
确定「选择」，也就是导致「状态」产生变化的行为。
会递归计算每一个选项最终的值是多少，再去选择；
⽬标⾦额为什么变化呢，因为你在选择硬币，你每选择⼀枚硬币，就相当于减少了⽬标⾦额。所以说所有硬币的面值，就是你的「选择」。
明确 dp 函数/数组的定义。我们这⾥讲的是⾃顶向下的解法，所以会有⼀个递归的 dp 函数，⼀般来说函数的参数就是状态转移中会变化的量，也就是「状态」；
函数的返回值就是题目要求我们计算的量。
就本题来说，状态只有⼀个，即 「目标金额」 ，题目要求我们计算凑出⽬标⾦额所需的最少硬币数量。
所以我们可以这样定义 dp 函数：dp(n) 表示，输⼊⼀个⽬标⾦额 n，返回凑出⽬标⾦额 n 所需的最少硬币数量。

伪代码：

要知道凑出11的硬币个数，若知道凑出6、9、10 的硬币个数（3个子问题）再加1就可以；
能画出递归树，问题必须符合最优子结构，能通过子问题推出原问题答案！

暴力递归：

状态方程：

即

存在重叠子问题！
重复节点下面都是重复计算；

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 终止条件
        if(amount==0){
            return 0;
        }
        if(amount<0){
            return -1;
        }
        int res=Integer.MAX_VALUE;
        for(int k:coins){
            //接收子问题结果，递归 回溯 ！
            int subProb=coinChange(coins,amount-k);
            //子问题无解
            if(subProb==-1){
                continue;
            }
            res=Math.min(res,subProb+1);
        }
        res= res==Integer.MAX_VALUE? -1:res;
        return res;
    }
}

自顶向下、带备忘录的递归：

dp函数定义：凑出amount金额，共需要 dp(coins,amount)枚硬币；
memo[amount] 定义也就是凑出amount数量的钱需要的最小硬币数量；
子结构就是凑出amout-k的最小金额，选择子问题的min值，最后加1就是凑出amout金额的最小个数；

class Solution {
    int memo[];
    public int coinChange(int[] coins, int amount) {
        memo=new int[amount+1];
        Arrays.fill(memo,-111); //初始化memo以免弄混
        return dp(coins,amount);
    }
// dp函数定义：凑出amount金额，共需要 dp(coins,amount)枚硬币；
    int dp(int[] coins,int amount ){
        //base case
        if(amount==0){
            return 0;
        }
        if(amount<0){
            return -1;
        }
        // 重叠子问题
        if(memo[amount]!=-111){
            return memo[amount];
        }
        int res=666666;
        //  最优子结构 状态转移  
        for(int k:coins){
        	// 要过滤不正常的，所以先temp记录结果
            int temp=dp(coins,amount-k); // 状态方程 Ⅰ
            if(temp==-1){ // 因为要剔除 -1的情况，所以拆开了状态方程
                continue;
            }
            res=Math.min(res,temp+1); // 选择，状态方程 Ⅱ
        }
        // 记录子问题最值到备忘录
         if(res!=666666){
            memo[amount]=res;
        }else{
            memo[amount]=-1; // 有问题的也要存进memo !
        }
        return memo[amount];
    }
}

递归时间复杂度=递归次数 x 递归函数本身复杂度
假设硬币列表有k个，递归函数本身复杂度是O(k)，
假设状态amount为n，则状态最多有0到n即n种，且有备忘录保证不会重复，使用递归穷举即递归了n次，所以时间复杂度最终为O(k) x O(n)=O(n)

自底向上

数组定义：即要想凑出amount金额，就用子问题结果+1；
金额amount最多即需要amount枚硬币凑出（全是金额为1的），所以共0-amount种状态；

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1]; // amount是状态，最多也就0-amount种状态
        Arrays.fill(dp,666666); //由于求的是min,dp初始化不能初始化为负数

        // base case
        dp[0]=0;
        // 外层for遍历所有状态
        for(int i=0;i<dp.length;i++){
            //内层for遍历计算所有最小值---做选择
            for(int k:coins){
                if( (i-k)<0 ){
                    continue;
                }
                //状态转移 
                dp[i]=Math.min(dp[i],1+dp[i-k]); // 直接用dp[i-k]，避免重叠子问题
            }
        }
        if(dp[amount]==666666){ // 结果为初始值则直接返回-1
            return -1;
        }else{
            return dp[amount];
        }
    }
}