int res = Integer.MIN_VALUE;
/* 输入一组气球，返回戳破它们获得的最大分数 */
int maxCoins(int[] nums) {
    backtrack(nums, 0);
    return res;
}
/* 回溯算法的伪码解法 */
void backtrack(int[] nums, int socre) {
    if (nums 为空) {
        res = Math.max(res, score);
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        int point = nums[i-1] * nums[i] * nums[i+1];
        int temp = nums[i];
        // 做选择
        在 nums 中删除元素 nums[i]
        // 递归回溯
        backtrack(nums, score + point);
        // 撤销选择
        将 temp 还原到 nums[i]
    }
}

public int minDistance(String word1, String word2) {
        return dp(word1, word2, word1.length() - 1, word2.length() - 1);
    }

    //返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
    int dp(String s1, String s2, int i, int j) {
        // base case
        if (i == -1) return j + 1;
        if (j == -1) return i + 1;

        if (s1.charAt(i) == s2.charAt(j)) {
            // 本来就相等，不需要任何操作
            // s1[0..i] 和 s2[0..j] 的最小编辑距离等于
            // s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离
            // 也就是说 dp(i, j) 等于 dp(i-1, j-1)
            return dp(s1, s2, i - 1, j - 1);  // 啥都不做
        } else {
            // 插入
            // 直接在 s1[i] 插入一个和 s2[j] 一样的字符
            // 那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比
            // 操作数加一

            // 删除
            // 直接把 s[i] 这个字符删掉
            // 前移 i，继续跟 j 对比
            // 操作数加一

            // 替换
            // 直接把 s1[i] 替换成 s2[j]，这样它俩就匹配了
            // 同时前移 i，j 继续对比
            // 操作数加一
            return Math.min(
                    Math.min(dp(s1, s2, i, j - 1) + 1,    // 插入
                            dp(s1, s2, i - 1, j) + 1),    // 删除
                    dp(s1, s2, i - 1, j - 1) + 1 // 替换
            );
        }
    }

static int i = 0;
 public int calculate(String s) {
     /*
         将 减法、乘法、除法 转换为 加法
         某个数 num, 如果前面的对应的运算符是 -，那么 将 -num 压入栈中
         这样，我们只需在最后将栈的元素全部弹出，完成加法操作，即可得到最终结果

         对于括号，它存在递归性质
         即
         3 * (2 + 4 * 3) + 2
       = 3 * calculate(2 + 4 * 3) + 2
       = 3 * 14 + 2
       即我们可以将括号内的字符串当作一个运算式，再递归调用本函数，最终返回一个数值
     */
     return dfs(s);
 }

 private int dfs(String s) {
     Deque<Integer> stack = new LinkedList<>();

     //记录某个连续的数，比如 "42"，那么我们首先 num = 4，然后遇到 2 ,num = num * 10 + 2 = 42
     int num = 0;
     char op = '+';
     for (; i < s.length(); i++) {
         char ch = s.charAt(i);

         //遇到左括号，递归运算内部子式
         if (ch == '(') {
             ++i;
             num = dfs(s);
         }

         if (Character.isDigit(ch)) {
             num = num * 10 + (ch - '0');
         }
         //不是数字，不是空格（运算符 或 '(' 或 ')' ） 或者 到了最后一个字符，那么根据前面记录的 op 操作符 将数字压栈，然后将新的运算符 ch 赋值给 op
         if (!Character.isDigit(ch) && ch != ' ' || i == s.length() - 1) {
             switch (op) {
                 case '+':
                     stack.push(num);
                     break;
                 case '-':
                     stack.push(-num);
                     break;
                 case '*':
                     int pre = stack.pop();
                     stack.push(pre * num);
                     break;
                 case '/':
                     pre = stack.pop();
                     stack.push(pre / num);
                     break;
             }
             num = 0;
             op = ch;
         }
         /*
         遇到右括号，退出循环，然后计算结果， 返回上一层 dfs
         这一步写在最后是因为，当 ch 为 右括号 时，那么我们需要先将前面已经得到的 num 压入栈中，再退出循环
         */
         if (ch == ')') {
             break;
         }
     }
     int res = 0;
     while (!stack.isEmpty()) {
         res += stack.pop();
     }
     return res;
 }

Map<String, Integer> map = new HashMap<>();
int dp(int K, int N) {
        int res = Integer.MAX_VALUE;
        if (K == 1) return N;
        if (N == 0) return 0;
        if (map.containsKey(K + "*" + N)) {
            return map.get(K + "*" + N);
        }
        for (int i = 1; i < N + 1; i++) {
            // 最坏情况下的最少扔鸡蛋次数
            res = Math.min(res,
                    //最坏情况下
                    Math.max(dp(K, N - i), // 没碎
                            dp(K - 1, i - 1)) //碎
                            + 1 //在第 i 楼扔了一次
            );
        }
        map.put(K + "*" + N, res);
        return res;
    }

Map<String, Integer> map = new HashMap<>();
public int dp2(int K, int N) {
        if (!map.containsKey(K+"*"+N)) {
            int ans;
            if (N == 0)
                ans = 0;
            else if (K == 1)
                ans = N;
            else {
                int lo = 1, hi = N;
                while (lo + 1 < hi) {
                    int x = (lo + hi) / 2;
                    int t1 = dp(K - 1, x - 1);
                    int t2 = dp(K, N - x);

                    if (t1 < t2)
                        lo = x;
                    else if (t1 > t2)
                        hi = x;
                    else
                        lo = hi = x;
                }

                ans = 1 + Math.min(Math.max(dp(K - 1, lo - 1), dp(K, N - lo)),
                        Math.max(dp(K - 1, hi - 1), dp(K, N - hi)));
            }

            map.put(K+"*"+N, ans);
        }

        return map.get(K+"*"+N);
    }