题目

**给定一个数组，代表每个人喝完咖啡准备刷杯子的时间
只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯
每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发
返回让所有咖啡杯变干净的最早完成时间
三个参数: int[] arr、int a、 int b**

注意，咖啡杯虽然可以并行挥发，但是咖啡机只能串行洗杯子，而且一旦杯子决定放入咖啡机洗的话，它就不能自己挥发干净了！！！

暴力方法

// drinks 喝完咖啡的时间 固定变量
    // a 洗一个咖啡杯的时间 固定变量
    // b 咖啡杯自己挥发干净的时间 固定变量
    // washLine 表示咖啡机何时可用
    // 0~index-1的杯子都洗干净了 
    // index及其往后所有的杯子要洗干净 返回最少的时间点
    public static int process(int[] drinks,int a,int b,int index,int washLine) {
        if(index==drinks.length-1) {
            // 来到最后一个杯子，我可以选择洗或者让其自动挥发干净
            // 洗的话，喝完这杯咖啡的时间点 和 咖啡机可用的时间点 取最大值，再加上洗杯子的时间
            // 自动挥发，喝完这杯咖啡的时间点 再 加上挥发的时间
            return Math.min(Math.max(drinks[index], washLine)+a, drinks[index]+b);
        }
        // if没中，剩下不止一杯咖啡
        
        // wash 洗当前这杯咖啡，结束的时间点
        int wash=Math.max(drinks[index], washLine)+a;
        // index+1及其往后所有杯子洗干净的时间，不包含index
        int next1=process(drinks, a, b, index+1, wash);
        // index及其往后所有杯子洗干净的时间
        // 因为是要等所有杯子都要变干净，所以取最大值
        int p1=Math.max(wash, next1);
        
        // dry 当前这杯咖啡挥发干净的时间点
        int dry=drinks[index]+b;
        // index+1及其往后所有杯子挥发干净的时间，不包含index
        // 自己挥发并不会占用咖啡机
        int next2=process(drinks, a, b, index+1, washLine);
        // index及其往后所有杯子挥发干净的时间
        int p2=Math.max(dry, next2);
        
        return Math.min(p1, p2);
    }

动态规划

从上面暴力尝试的过程中发现可变参数其实只有两个，index和washLine。

base case就是index到N-1的时候，所以index的变化范围是0~N-1

washLine的变化范围分析不出来，这时候还原到原题意里面，看看它最夸张的值是多少？washLine最夸张的值就是所有咖啡杯全部都用咖啡机洗的时候！所以这个题是寻找业务限制的尝试模型。

public static int dp(int[] drinks,int a,int b) {
        // 如果洗杯子的时间大于等于杯子自己挥发干净的时间
        // 那么就没必要洗，也没必要改动态规划
        // 最后一杯咖啡挥发的时间就是所有咖啡杯变干净的最早完成时间
        int N=drinks.length;
        if(a>=b) {
            return drinks[N-1]+b;
        }
        // a<b 才有必要改动态规划
        // limit 咖啡机何时可用
        int limit=0;
        for(int i=0; i<N; i++) {
            // 所有咖啡杯遍历完成后，limit就是全部洗完的极限
            limit=Math.max(limit,drinks[i])+a;
        }
        int[][] dp=new int[N][limit+1];
        // 填N-1行的所有值
        for(int washLine=0; washLine<=limit; washLine++) {
            dp[N-1][washLine]=Math.min(Math.max(drinks[N-1], washLine)+a, drinks[N-1]+b);
        }
        // 填任何一个普遍位置 从下到上，从左到右
        for(int index=N-2; index>=0; index--) {
            for(int washLine=0; washLine<=limit; washLine++) {
                int p1=Integer.MAX_VALUE;
                int wash=Math.max(drinks[index],washLine)+a;
                if(wash<=limit) {
                    p1=Math.max(dp[index+1][wash], wash);
                }
                int p2=Math.max(drinks[index]+b,dp[index+1][washLine]);
                dp[index][washLine]=Math.min(p1, p2);
            }
        }
        return dp[0][0];
    }

最后，来点方法论的总结：

总的来说以下三条主线非常重要：

1）暴力递归改出来后如何优化
2）设计暴力递归过程中，如何知道自己设计的东西靠不靠谱
3）根据固定的四个模型，往下编

再强调一下，任何动态规划都是从最自然智慧的暴力递归出发弄出来的！

什么暴力递归可以继续优化?
有重复调用同一个子问题的解，这种递归可以优化。如果每一个子问题都是不同的解，无法优化也不用优化。

暴力递归和动态规划的关系
某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划。任何动态规划问题，都一定对应着某一个有解的重复调用的暴力递归。但不是所有的暴力递归，都一定对应着动态规划。

面试题和动态规划的关系
解决一个问题，可能有很多尝试方法，可能在很多尝试方法中，又有若干个尝试方法有动态规划的方式。一个问题可能有若干种动态规划的解法。

如何找到某个问题的动态规划方式?
1)设计暴力递归:重要原则+4种常见尝试模型!重点!
2)分析有没有重复解:套路解决
3)用记忆化搜索->用严格表结构实现动态规划:套路解决
4)看看能否继续优化:套路解决

面试中设计暴力递归过程的原则
1)每一个可变参数的类型，一定不要比int类型更加复杂
2) 原则1)可以违反，让类型突破到一维线性结构，那必须是单一可变参数
3)如果发现原则1)被违反，但不违反原则2)，只需要做到记忆化搜索即可
4)可变参数的个数，能少则少

知道了面试中设计暴力递归过程的原则，然后呢?
一定要逼自己找到不违反原则情况下的暴力尝试!
如果你找到的暴力尝试，不符合原则，马上舍弃!找新的!
如果某个题目突破了设计原则，一定极难极难，面试中出现概率低于5%!

常见的4种尝试模型
1)从左往右的尝试模型
2)范围上的尝试模型
3)多样本位置全对应的尝试模型
4)寻找业务限制的尝试模型

如何分析有没有重复解
列出调用过程，可以只列出前几层，有没有重复解，一看便知

暴力递归到动态规划的套路
1)你已经有了一个不违反原则的暴力递归，而且的确存在解的重复调用
2)找到哪些参数的变化会影响返回值，对每一个列出变化范围
3)参数间的所有的组合数量，意味着表大小
4)记忆化搜索的方法就是傻缓存，非常容易得到
5)规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解
6)对于有枚举行为的决策过程，进一步优化

动态规划的进一步优化
1)空间压缩
2)状态化简
3)四边形不等式
其他优化技巧略

暴力递归之所以暴力是因为有大量重复计算在浪费时间

动态规划就是某一类尝试行为的进一步优化，任何一个动态规划的问题都是以某一个暴力尝试过程中优化后的样子