第18节.pptx

动态—》动态规划思路

什么类型的递归可以优化

  • 有重复调用同一个子问题的解，这种递归可以优化

  • 如果每一个子问题都是不同的解，无法优化也不用优化

    递归与动态规划关系

  • 某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划

  • 任何动态规划问题，都一定对应着某一个有重复过程的暴力递归
  • 但不是所有的暴力递归，都一定对应着动态规划

    如何找到某个问题的动态规划方案

  1. 设计暴力递归：重要原则+4种常见尝试模型！重点！
  2. 分析有没有重复解：套路解决
  3. 用记忆化搜索 -> 用严格表结构实现动态规划：套路解决

  4. 看看能否继续优化：套路解决

    设计暴力递归的原则

  5. 每一个可变参数的类型，一定不要比int类型更加复杂

  6. 原则1可以违反，让类型突破到一维线性结构，那必须是单一可变参数
  7. 如果发现原则1被违反，但不违反原则2只需要做到记忆化搜索即可

  8. 可变参数的个数，能少则少

    常见4中尝试模型

  9. 从左往右的尝试模型

  10. 范围上的尝试模型
  11. 多样本位置全对应的尝试模型
  12. 寻找业务限制的尝试模型

  13. 进一步优化：

    1. 空间压缩
    2. 状态化简
    3. 四边形不等式
    4. 其他优化技巧

      暴力递归改动态规划套路

  14. 你已经有了一个不违反原则的暴力递归，而且的确存在解的重复调用

  15. 找到哪些参数的变化会影响返回值，对每一个列出变化范围
  16. 参数间的所有的组合数量，意味着表大小
  17. 记忆化搜索的方法就是傻缓存，非常容易得到
  18. 规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解
  19. 对于有枚举行为的决策过程，进一步优化

    递归—》动态规划题目

    题目1：机器人的步数

    假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
    开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
    如果机器人来到1位置，那么下一步只能往右来到2位置；
    如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
    如果机器人来到中间位置，那么下一步可以往左走或者往右走；
    规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
    给定四个参数 N、M、K、P，返回方法数。 ```java

//假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2 //开始时机器人在其中的M位置上(M 一定是 1~N 中的一个) //如果机器人来到1位置，那么下一步只能往右来到2位置； //如果机器人来到N位置，那么下一步只能往左来到 N-1 位置； //如果机器人来到中间位置，那么下一步可以往左走或者往右走； //规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种 //给定四个参数 N、M、K、P，返回方法数。

// 暴力递归方式

/**

  • @param n 一排有n个位置
  • @param m 开始时机器人在m位置
  • @param k 机器人必须走k步
  • @param p 最终需要到的位置
  • @return 方法数 */ public static int robotWalkWays(int n, int m, int k, int p) { if (m < 0 || m > n || k <= 0 || p <= 0 || p > n) {
    1.   return -1;
    } return process(n, m, k, p);

}

/**

  • @param n 一排有n个位置
  • @param cur 当前机器人所在位置
  • @param k 剩余k步
  • @param p 目标位置
  • @return 方法数 */ public static int process(int n, int cur, int k, int p) { if (k == 0) {
      return cur == p ? 1 : 0;
    } if (cur == 1) {
      return process(n, 2, k - 1, p);
    } if (cur == n) {
      return process(n, n - 1, k - 1, p);
    } return process(n, cur - 1, k - 1, p) + process(n, cur + 1, k - 1, p); } java // 优化1，加入缓存表 /*
    • ① process(4,2,4,4) ——》 process(4,1,3,4) + process(4,3,3,4)
    • ② process(4,1,3,4) ——》 process(4,2,2,4)
    • process(4,3,3,4) ——》 process(4,2,2,4) + process(4,4,2,4)
    • ③ process(4,2,2,4) ——》process(4,1,1,4)+process(4,3,1,4)
    • process(4,2,2,4) ——》process(4,1,1,4)+process(4,3,1,4)
    • process(4,4,2,4) ——》process(4,3,1,4) *
    • 出现大量重复计算的值，因此加入缓存表，减少重复计算
    • */

/**

  • @param n 一排有n个位置 [1~n]
  • @param m 开始时机器人在m位置
  • @param k 机器人必须走k步
  • @param p 最终需要到的位置

  • @return 方法数 */ public static int robotWalkWays2(int n, int m, int k, int p) { if (m < 0 || m > n || k <= 0 || p <= 0 || p > n) {

     return -1;

    } int[][] map = new int[n + 1][k + 1];

    // 初始化map，值为-1表示当前值没有计算过 for (int[] arr : map) {

     Arrays.fill(arr, -1);

    } return process2(n, m, k, p, map);

}

/**

  • @param n 一排有n个位置
  • @param cur 当前机器人所在位置
  • @param k 剩余k步
  • @param p 目标位置
  • @param map 缓存表
  • @return 方法数 */ public static int process2(int n, int cur, int k, int p, int[][] map) { if (map[cur][k] != -1) {
     return map[cur][k];
    } int ans = 0; if (k == 0) {
     ans = cur == p ? 1 : 0;
    } else if (cur == 1) {
     ans = process2(n, 2, k - 1, p, map);
    } else if (cur == n) {
     ans = process2(n, n - 1, k - 1, p, map);
    } else {
     ans = process2(n, cur - 1, k - 1, p, map) + process2(n, cur + 1, k - 1, p, map);
    } map[cur][k] = ans; return ans; } ![](https://cdn.nlark.com/yuque/0/2022/jpeg/1636836/1650432688326-487d841f-a4b3-420e-8c1e-417780054c81.jpeg)java // 优化3 直接对map赋值

/**

  • @param n 一排有n个位置 [1~n]
  • @param m 开始时机器人在m位置
  • @param k 机器人必须走k步
  • @param p 最终需要到的位置
  • @return 方法数 */ public static int robotWalkWays3(int n, int m, int k, int p) { if (m < 0 || m > n || k <= 0 || p <= 0 || p > n) {
     return -1;
    } int[][] map = new int[n + 1][k + 1]; map[p][0] = 1; for (int c = 1; c <= k; c++) {
     map[1][c] = map[2][c - 1];
 for (int i = 2; i < n; i++) {
     map[i][c] = map[i - 1][c - 1] + map[i + 1][c - 1];
 }
 map[n][c] = map[n - 1][c - 1];
    } return map[m][k]; } ```

    题目2：获胜者分数

    给定一个整型数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌。规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明，请返回最后获胜者的分数。 ```java //给定一个整型数组arr，代表数值不同的纸牌排成一条线,玩家A和玩家B依次拿走每张纸牌 //规定玩家A先拿，玩家B后拿,但是每个玩家每次只能拿走最左或最右的纸牌 //玩家A和玩家B都绝顶聪明,请返回最后获胜者的分数。

public static int winnerPoint1(int[] arr) { if (arr == null || arr.length == 0) { return 0; } int first = f1(arr, 0, arr.length - 1); int second = g1(arr, 0, arr.length - 1); System.out.println(“先手分数：” + first + “ 后手分数：” + second); System.out.println(first > second ? “先手获胜” : “后手获胜”); return Math.max(first, second); }

/**

  • 表示先手时获取的最大分数 *
  • @param arr 纸牌数组
  • @param l 数组最左边
  • @param r 数组最右边
  • @return 获取的最大分数 */ private static int f1(int[] arr, int l, int r) { // 只有1张牌，先手就获得这张牌 if (l == r) {
     return arr[l];
    } // 先手 获得左边的牌的分数和获得右边牌的分数的最大值 int left = arr[r] + g1(arr, l, r - 1); int right = arr[l] + g1(arr, l + 1, r); return Math.max(left, right); }

/**

  • 表示后手时获得的最大分数 *
  • @param arr 纸牌数组
  • @param l 数组最左边
  • @param r 数组最右边
  • @return 获取的最大分数 */ private static int g1(int[] arr, int l, int r) { // 只有1张牌，后手获得分数为0 if (l == r) {
     return 0;
    } // 表示先手获取了左边的排，在剩下的范围获取最大值 int left = f1(arr, l + 1, r); // 表示先手获取了右边的排，在剩下的范围获取最大值 int right = f1(arr, l, r - 1); // 因为是后手，只能获得两者分数小的 return Math.min(left, right); } java // 优化1 分析

/* 以 int[] a = {11, 15, 22, 3} 为例进行分析

  • 先手：f(a,0,3) = Math.max(a[0]+g(a,1,3),a[3]+g(a,0,2)) *
  • g(a,1,3) = Math.min(f(a,2,3),f(a,1,2)) *
  • f(a,2,3) = Math.max(a[2]+g(a,3,3),a[3]+g(a,2,2))
  • f(a,1,2) = Matj.max(a[1]+g(a,2,2),a[2]+g(a,1,1)) *
  • g(a,0,2) = Math.min(f(a,0,1),f(a,1,2)) *
  • f(a,0,1)= Math.mxa(a[0]+g(a,1,1),a[1]+g(a,0,0)
  • f(a,1,2)= Math.mxa(a[1]+g(a,2,2),a[2]+g(a,1,1) *
  • 后手：g(a,0,3) = Math.min(f(a,1,3),f(a,0,2)) *
  • f(a,1,3) = Math.max(a[1]+g(a,2,3),a[3]+g(a,1,2)) *
  • g(a,2,3) = Math.min(f(a,3,3),f(a,2,2)
  • g(a,1,2) = Math.min(f(a,1,1),f(a,2,2) *
  • f(a,0,2) = Math.max(a[0]+g(a,1,2),a[2]+g(a,0,1)) *
  • g(a,1,2) = Math.min(f(a,1,1),f(a,2,2)
  • g(a,0,1) = Math.min(f(a,0,0),f(a,1,1) *
  • 通过以上分析，有重复计算的值，因此加入缓存表，避免重复计算
  • */

public static int winnerPoint2(int[] arr) { if (arr == null || arr.length == 0) { return 0; } int[][] firstMap = new int[arr.length][arr.length]; int[][] secondMap = new int[arr.length][arr.length];

for (int i = 0; i < arr.length; i++) {
    Arrays.fill(firstMap[i], -1);
    Arrays.fill(secondMap[i], -1);
}

int first = f2(arr, 0, arr.length - 1, firstMap, secondMap);
int second = g2(arr, 0, arr.length - 1, firstMap, secondMap);
System.out.println("先手分数：" + first + "  后手分数：" + second);
System.out.println(first > second ? "先手获胜" : "后手获胜");
return Math.max(first, second);

}

/**

  • 表示先手时获取的最大分数 *
  • @param arr 纸牌数组
  • @param l 数组最左边
  • @param r 数组最右边

  • @return 获取的最大分数 */ private static int f2(int[] arr, int l, int r, int[][] firstMap, int[][] secondMap) {

    if (firstMap[l][r] != -1) {

     return firstMap[l][r];

    } // 只有1张牌，先手就获得这张牌 int ans = -1; if (l == r) {

     ans = arr[l];

    } else {

     // 先手 获得左边的牌的分数和获得右边牌的分数的最大值
 int left = arr[r] + g1(arr, l, r - 1);
 int right = arr[l] + g1(arr, l + 1, r);
 ans = Math.max(left, right);

    } firstMap[l][r] = ans; return ans; }

/**

  • 表示后手时获得的最大分数 *
  • @param arr 纸牌数组
  • @param l 数组最左边
  • @param r 数组最右边

  • @return 获取的最大分数 */ private static int g2(int[] arr, int l, int r, int[][] firstMap, int[][] secondMap) {

    if (secondMap[l][r] != -1) {

     return secondMap[l][r];

    } int ans = -1; // 只有1张牌，后手获得分数为0 if (l == r) {

     ans = 0;

    } else {

     // 表示先手获取了左边的排，在剩下的范围获取最大值
 int left = f1(arr, l + 1, r);
 // 表示先手获取了右边的排，在剩下的范围获取最大值
 int right = f1(arr, l, r - 1);
 // 因为是后手，只能获得两者分数小的
 ans = Math.min(left, right);

    } secondMap[l][r] = ans; return ans; }

![](https://cdn.nlark.com/yuque/0/2022/jpeg/1636836/1650437604913-0acbaa92-6ee2-4c53-b10c-fee38bb27fd7.jpeg)
```java
// 优化3 直接对map赋值

public static int winnerPoint3(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int n = arr.length;
    int[][] firstMap = new int[n][n];
    int[][] secondMap = new int[n][n];
    for (int i = 0; i < n; i++) {
        firstMap[i][i] = arr[i];
    }

    for (int col = 1; col < n; col++) {
        for (int l = 0, r = col; r < n; l++, r++) {
            secondMap[l][r] = Math.min(firstMap[l][r - 1], firstMap[l + 1][r]);
            firstMap[l][r] = Math.max(arr[l] + secondMap[l + 1][r], arr[r] + secondMap[l][r - 1]);
        }
    }
    int first = firstMap[0][n - 1];
    int second = secondMap[0][n - 1];
    System.out.println("先手分数：" + first + "  后手分数：" + second);
    System.out.println(first > second ? "先手获胜" : "后手获胜");
    return Math.max(first, second);
}

第19节.pptx

题目3：背包装的最大价值

给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。
给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。
返回你能装下最多的价值是多少? 

//给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。
//给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。
//返回你能装下最多的价值是多少?


public static int mostValuable(int[] weights, int[] values, int bag) {
    if (weights == null || values == null || weights.length == 0 || values.length == 0 || weights.length != values.length || bag < 0) {
        return 0;
    }

    return process(weights, values, 0, bag);
}

/**
* 返回最大价值
*
* @param weights 物品种量
* @param values  物品价值
* @param i       当前物品位置
* @param bag     背包剩余数量
* @return 获得的最大价值
*/
private static int process(int[] weights, int[] values, int i, int bag) {
    if (bag < 0) {
        return -1;
    }
    if (i == weights.length) {
        return 0;
    }
    // 没有选当前位置的物品
    int p1 = process(weights, values, i + 1, bag);
    // 选了当前的物品
    int p2 = 0;
    if (bag - weights[i] >= 0) {
        p2 = values[i] + process(weights, values, i + 1, bag - weights[i]);
    }
    return Math.max(p1, p2);
  }


// 优化1
/*
*process(weights,values,0,bag) -> process(weights,values,1,bag),process(weights,values,1,bag-weights[0])
*
*  process(weights,values,1,bag) -> process(weights,values,2,bag),process(weights,values,2,bag-weights[1])
*  process(weights,values,1,bag-weights[0]) ->  process(weights,values,2,bag-weight[0]),process(weights,values,1,bag-weights[0]-weight[1])
*   如果： bag-weights[1] = bag-weight[0]，那么process(weights,values,2,bag-weights[1])与 process(weights,values,2,bag-weight[0]) 重复
*
*  加入缓存表进行优化
* */

public static int mostValuable2(int[] weights, int[] values, int bag) {
    if (weights == null || values == null || weights.length == 0 || values.length == 0 || weights.length != values.length || bag < 0) {
        return 0;
    }
    int n = weights.length;
    int[][] map = new int[n + 1][bag + 1];
    for (int[] arr : map) {
        Arrays.fill(arr, -1);
    }
    return process2(weights, values, 0, bag, map);
}

/**
* 返回最大价值
*
* @param weights 物品种量
* @param values  物品价值
* @param i       当前物品位置
* @param bag     背包剩余数量
* @return 获得的最大价值
*/
private static int process2(int[] weights, int[] values, int i, int bag, int[][] map) {
    if (bag < 0) {
        return -1;
    } else if (i == weights.length) {
        return 0;
    } else if (map[i][bag] != -1) {
        return map[i][bag];
    } else {
        int ans = 0;
        // 没有选当前位置的物品
        int p1 = process2(weights, values, i + 1, bag, map);
        // 选了当前的物品
        int p2 = 0;
        if (bag - weights[i] >= 0) {
            p2 = values[i] + process2(weights, values, i + 1, bag - weights[i], map);
        }
        ans = Math.max(p1, p2);
        map[i][bag] = ans;
        return ans;
    }
}


// 优化3 转化为动态规划表

public static int mostValuable3(int[] weights, int[] values, int bag) {
    if (weights == null || values == null || weights.length == 0 || values.length == 0 || weights.length != values.length || bag < 0) {
        return 0;
    }
    int n = weights.length;
    int[][] map = new int[n + 1][bag + 1];

    for (int i = n - 1; i >= 0; i--) {
        for (int res = 0; res <= bag; res++) {
            int p1 = map[i + 1][res];
            int p2 = 0;
            if (res - weights[i] >= 0) {
                p2 = values[i] + map[i + 1][res - weights[i]];
            }
            map[i][res] = Math.max(p1, p2);
        }
    }
    return map[0][bag];
}

题目4：数字字符串转换字母字符串，多少种转换结果

规定1和A对应、2和B对应、3和C对应…26和Z对应，那么一个数字字符串比如”111”就可以转化为:”AAA”、”KA”和”AK”。给定一个只有数字字符组成的字符串str，返回有多少种转化结果 

//规定1和A对应、2和B对应、3和C对应...26和Z对应，那么一个数字字符串比如"111”就可以转化为:"AAA"、"KA"和"AK"。
// 给定一个只有数字字符组成的字符串str，返回有多少种转化结果

public static int convertToLetterSting(String str) {
    if (str == null || str.length() == 0) {
        return 0;
    }

    char[] chars = str.toCharArray();
    return process(chars, 0);
}

/**
 * 从i位置开始，可以转换的最多情况
 *
 * @param chars 字符串数组
 * @param i     下标i
 * @return 可以转换的次数
 */
private static int process(char[] chars, int i) {
    // 找到1种转换方法
    if (i == chars.length) {
        return 1;
    }
    // 当前位置是0，无法直接转换，找到0种结果
    if (chars[i] == '0') {
        return 0;
    }
    // 后面位置有几种转换方法
    int way = process(chars, i + 1);
    // 当前位置和后一个位置组合起来的转换方法
    if (i + 1 < chars.length && (chars[i] - '0') * 10 + (chars[i + 1] - '0') < 27) {
        way += process(chars, i + 2);
    }
    return way;
}

//  优化 动态规划

public static int convertToLetterSting2(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }

    char[] chars = s.toCharArray();
    int n = chars.length;
    int[] map = new int[n + 1];
    map[n] = 1;
    for (int i = n - 1; i >= 0; i--) {
        if (chars[i] != '0') {
            int way = map[i + 1];
            if (i + 1 < n && (chars[i] - '0') * 10 + (chars[i + 1] - '0') < 27) {
                way += map[i + 2];
            }
            map[i] = way;
        }
    }
    return map[0];
}

题目5：最少贴纸数

给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文，arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来，返回需要至少多少张贴纸可以完成这个任务。
例子：str= “babac”，arr = {“ba”,”c”,”abcd”}，ba + ba + c 3 ， abcd + abcd 2 ， abcd+ba 2，所以返回2
https://leetcode.com/problems/stickers-to-spell-word/submissions/

//给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文，arr每一个字符串，代表一张贴纸，
// 你可以把单个字符剪开使用，目的是拼出str来，返回需要至少多少张贴纸可以完成这个任务。
//例子：str= "babac"，arr = {"ba","c","abcd"}，ba + ba + c  3 ， abcd + abcd 2 ， abcd+ba 2，所以返回2


public static int minStickers1(String[] stickers, String target) {
    if (stickers == null || stickers.length == 0 || target == null || target.length() == 0) {
        return 0;
    }
    return process1(stickers, target);
}

/**
 * 返回最少张数
 *
 * @param stickers 贴纸
 * @param target   目标
 * @return 最少张数
 */
private static int process1(String[] stickers, String target) {
    if (target.length() == 0) {
        return 0;
    }
    int min = Integer.MAX_VALUE;
    for (String sticker : stickers) {
        String rest = minus(target, sticker);
        if (rest.length() != target.length()) {
            min = Math.min(min, process1(stickers, rest));
        }
    }
    return min + (min == Integer.MAX_VALUE ? 0 : 1);
}

private static String minus(String s1, String s2) {
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    int[] count = new int[26];
    for (char cha : str1) {
        count[cha - 'a']++;
    }
    for (char cha : str2) {
        count[cha - 'a']--;
    }
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < 26; i++) {
        if (count[i] > 0) {
            for (int j = 0; j < count[i]; j++) {
                builder.append((char) (i + 'a'));
            }
        }
    }
    return builder.toString();
}

public static int minStickers2(String[] stickers, String target) {
    if (stickers == null || stickers.length == 0 || target == null || target.length() == 0) {
        return 0;
    }
    int n = stickers.length;
    // 关键优化(用词频表替代贴纸数组)
    int[][] counts = new int[n][26];
    for (int i = 0; i < n; i++) {
        char[] str = stickers[i].toCharArray();
        for (char cha : str) {
            counts[i][cha - 'a']++;
        }
    }
    int ans = process2(counts, target);
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

// stickers[i] 数组，当初i号贴纸的字符统计 int[][] stickers -> 所有的贴纸
// 每一种贴纸都有无穷张
// 返回搞定target的最少张数
// 最少张数
public static int process2(int[][] stickers, String t) {
    if (t.length() == 0) {
        return 0;
    }
    // target做出词频统计
    // target  aabbc  2 2 1..
    //                0 1 2..
    char[] target = t.toCharArray();
    int[] tCounts = new int[26];
    for (char cha : target) {
        tCounts[cha - 'a']++;
    }
    int n = stickers.length;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        // 尝试第一张贴纸是谁
        int[] sticker = stickers[i];
        // 最关键的优化(重要的剪枝!这一步也是贪心!)
        if (sticker[target[0] - 'a'] > 0) {
            StringBuilder builder = new StringBuilder();
            for (int j = 0; j < 26; j++) {
                if (tCounts[j] > 0) {
                    int nums = tCounts[j] - sticker[j];
                    for (int k = 0; k < nums; k++) {
                        builder.append((char) (j + 'a'));
                    }
                }
            }
            String rest = builder.toString();
            min = Math.min(min, process2(stickers, rest));
        }
    }
    return min + (min == Integer.MAX_VALUE ? 0 : 1);
}

public static int minStickers3(String[] stickers, String target) {
    int N = stickers.length;
    int[][] counts = new int[N][26];
    for (int i = 0; i < N; i++) {
        char[] str = stickers[i].toCharArray();
        for (char cha : str) {
            counts[i][cha - 'a']++;
        }
    }
    HashMap<String, Integer> dp = new HashMap<>();
    dp.put("", 0);
    int ans = process3(counts, target, dp);
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

public static int process3(int[][] stickers, String t, HashMap<String, Integer> dp) {
    if (dp.containsKey(t)) {
        return dp.get(t);
    }
    char[] target = t.toCharArray();
    int[] tCounts = new int[26];
    for (char cha : target) {
        tCounts[cha - 'a']++;
    }
    int n = stickers.length;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        int[] sticker = stickers[i];
        if (sticker[target[0] - 'a'] > 0) {
            StringBuilder builder = new StringBuilder();
            for (int j = 0; j < 26; j++) {
                if (tCounts[j] > 0) {
                    int nums = tCounts[j] - sticker[j];
                    for (int k = 0; k < nums; k++) {
                        builder.append((char) (j + 'a'));
                    }
                }
            }
            String rest = builder.toString();
            min = Math.min(min, process3(stickers, rest, dp));
        }
    }
    int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
    dp.put(t, ans);
    return ans;
}

题目6：最长公共子序列长度

给定两个字符串str1和str2，
返回这两个字符串的最长公共子序列长度
比如 ： str1=“a12b3c456d”,str2 = “1ef23ghi4j56k”
最长公共子序列是“123456”，所以返回长度6
https://leetcode.com/problems/longest-common-subsequence/

//给定两个字符串str1和str2，
//返回这两个字符串的最长公共子序列长度
//比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”
//最长公共子序列是“123456”，所以返回长度6


public static int longestCommonSubsequence1(String s1, String s2) {
    if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
        return 0;
    }
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    // 尝试
    return process1(str1, str2, str1.length - 1, str2.length - 1);
}

public static int process1(char[] str1, char[] str2, int i, int j) {
    if (i == 0 && j == 0) {
        return str1[i] == str2[j] ? 1 : 0;
    } else if (i == 0) {
        if (str1[i] == str2[j]) {
            return 1;
        } else {
            return process1(str1, str2, i, j - 1);
        }
    } else if (j == 0) {
        if (str1[i] == str2[j]) {
            return 1;
        } else {
            return process1(str1, str2, i - 1, j);
        }
    } else { // i != 0 && j != 0
        int p1 = process1(str1, str2, i - 1, j);
        int p2 = process1(str1, str2, i, j - 1);
        int p3 = str1[i] == str2[j] ? (1 + process1(str1, str2, i - 1, j - 1)) : 0;
        return Math.max(p1, Math.max(p2, p3));
    }
}

public static int longestCommonSubsequence2(String s1, String s2) {
    if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
        return 0;
    }
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    int n = str1.length;
    int m = str2.length;
    int[][] dp = new int[n][m];
    dp[0][0] = str1[0] == str2[0] ? 1 : 0;
    for (int j = 1; j < m; j++) {
        dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
    }
    for (int i = 1; i < n; i++) {
        dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            int p1 = dp[i - 1][j];
            int p2 = dp[i][j - 1];
            int p3 = str1[i] == str2[j] ? (1 + dp[i - 1][j - 1]) : 0;
            dp[i][j] = Math.max(p1, Math.max(p2, p3));
        }
    }
    return dp[n - 1][m - 1];
}

第20节.pptx

题目7：最长回文子序列

给定一个字符串str，返回这个字符串的最长回文子序列长度
比如 ： str=“a12b3c43def2ghi1kpm”，最长回文子序列是“1234321”或者“123c321”，返回长度7


// 算法1：获取str倒序字符串成str2，求str和str2的最长子序列

public static int longestPalindromicSubString(String string) {
    if (string == null || string.length() == 0) {
        return 0;
    }

    char[] chars = string.toCharArray();

    char[] reverseChar = new char[chars.length];

    int n = chars.length;
    for (int j = n - 1; j >= 0; j--) {
        reverseChar[n - 1 - j] = chars[j];
    }

    int[][] dp = new int[n][n];

    dp[0][0] = chars[0] == reverseChar[0] ? 1 : 0;

    // int[i][0]
    for (int i = 1; i < n; i++) {
        dp[i][0] = chars[i] == reverseChar[0] ? 1 : dp[i - 1][0];
    }
    // int[0][j]
    for (int j = 1; j < n; j++) {
        dp[0][j] = chars[0] == reverseChar[j] ? 1 : dp[0][j - 1];
    }
    // 一般位置的 int[i][j]
    for (int i = 1; i < n; i++) {
        for (int j = i; j < n; j++) {
            int p1 = dp[i - 1][j];
            int p2 = dp[i][j - 1];
            int p3 = chars[i] == chars[j] ? 1 + dp[i - 1][j - 1] : 0;
            dp[i][j] = Math.max(p1, Math.max(p2, p3));
        }
    }
    return dp[n - 1][n - 1];
}

// 算法2  样本对于模型

public static int longestPalindromicSubString2(String string) {
    if (string == null || string.length() == 0) {
        return 0;
    }
    char[] chars = string.toCharArray();
    return process(chars, 0, chars.length - 1);
}


private static int process(char[] chars, int i, int j) {
    // 1个字符
    if (i == j) {
        return 1;
    }
    // 2个字符
    if (i == j - 1) {
        return chars[i] == chars[j] ? 2 : 0;
    }
    // 其他情况
    // 回文以i开头，不以j结尾
    int p1 = process(chars, i, j - 1);
    // 回文不以i开头，以j结尾
    int p2 = process(chars, i + 1, j);
    // 回文必须以i开头,j结尾
    int p3 = chars[i] == chars[j] ? 2 + process(chars, i + 1, j - 1) : 0;
    return Math.max(p1, Math.max(p2, p3));
}


// 以上暴力递归直接改动态规划表

public static int longestPalindromicSubString3(String string) {
    if (string == null || string.length() == 0) {
        return 0;
    }

    char[] chars = string.toCharArray();
    int n = chars.length;
    int[][] dp = new int[n][n];

    dp[n - 1][n - 1] = 1;
    for (int i = 0; i < n - 1; i++) {
        // base case dp[i][j]  i==j时  dp[i][j]=1;
        dp[i][i] = 1;
        // base case dp[i][j]  i==j-1时 chars[i]==char[j]?2:0;
        dp[i][i + 1] = chars[i] == chars[i + 1] ? 2 : 0;
    }

    for (int i = n - 3; i >= 0; i--) {
        for (int j = i + 2; j < n; j++) {
            int p1 = dp[i][j - 1];
            int p2 = dp[i + 1][j];
            int p3 = chars[i] == chars[j] ? 2 + dp[i + 1][j - 1] : 0;
            dp[i][j] = Math.max(p1, Math.max(p2, p3));
        }
    }
    return dp[0][n - 1];
}

// 对位置进行优化

public static int longestPalindromicSubString4(String string) {
    if (string == null || string.length() == 0) {
        return 0;
    }

    char[] chars = string.toCharArray();
    int n = chars.length;
    int[][] dp = new int[n][n];

    dp[n - 1][n - 1] = 1;
    for (int i = 0; i < n - 1; i++) {
        // base case dp[i][j]  i==j时  dp[i][j]=1;
        dp[i][i] = 1;
        // base case dp[i][j]  i==j-1时 chars[i]==char[j]?2:0;
        dp[i][i + 1] = chars[i] == chars[i + 1] ? 2 : 0;
    }

    for (int i = n - 3; i >= 0; i--) {
        for (int j = i + 2; j < n; j++) {
            dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
            if (chars[i] == chars[j]) {
                dp[i][j] = Math.max(dp[i][j], 2 + dp[i + 1][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

题目8：象棋，马走“日”,走到规定位置方法数

请同学们自行搜索或者想象一个象棋的棋盘，然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
给你三个 参数 x，y，k
返回“马”从(0,0)位置出发，必须走k步
最后落在(x,y)上的方法数有多少种? 


/**
 * 返回
 *
 * @param x 横坐标上9条线，则x范围 0~8
 * @param y 纵坐标上10条线，则y范围 0~9
 * @param k 走的步数
 * @return 返回从(0, 0)出发，走到(x,y)的方法
 */
public static int horseJump1(int x, int y, int k) {
    if (x < 0 || x > 9 || y < 0 || y > 8 || k == 0) {
        return 0;
    }
    return process(x, y, 0, 0, k);
}

/**
 * @param x 目标
 * @param y 目标
 * @param i 当前横坐标
 * @param j 当前纵坐标
 * @param k 剩余步数
 * @return 返回从当前位置(i, j)，走k步，走到(x,y)的方法数
 */
private static int process(int x, int y, int i, int j, int k) {
    // 跳到棋盘外
    if (i < 0 || i > 9 || j < 0 || j > 8) {
        return 0;
    }
    // 剩余0步，当前位置是目标位置，返回1种走法
    if (k == 0) {
        return i == x && j == y ? 1 : 0;
    }
    // 其余位置有8种可能性
    int ans = 0;
    ans += process(x, y, i + 1, j + 2, k - 1);
    ans += process(x, y, i + 2, j + 1, k - 1);
    ans += process(x, y, i + 2, j - 1, k - 1);
    ans += process(x, y, i + 1, j - 2, k - 1);
    ans += process(x, y, i - 1, j + 2, k - 1);
    ans += process(x, y, i - 2, j + 1, k - 1);
    ans += process(x, y, i - 2, j - 1, k - 1);
    ans += process(x, y, i - 1, j - 2, k - 1);
    return ans;
}

// 暴力递归改动态规划
public static int horseJump2(int x, int y, int k) {
    if (x < 0 || x > 8 || y < 0 || y > 9 || k == 0) {
        return 0;
    }

    int[][][] dp = new int[10][9][k + 1];
    dp[x][y][0] = 1;
    for (int k0 = 1; k0 <= k; k0++) {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 9; j++) {
                dp[i][j][k0] += pick(dp, i + 1, j + 2, k0 - 1);
                dp[i][j][k0] += pick(dp, i + 2, j + 1, k0 - 1);
                dp[i][j][k0] += pick(dp, i + 2, j - 1, k0 - 1);
                dp[i][j][k0] += pick(dp, i + 1, j - 2, k0 - 1);
                dp[i][j][k0] += pick(dp, i - 1, j + 2, k0 - 1);
                dp[i][j][k0] += pick(dp, i - 2, j + 1, k0 - 1);
                dp[i][j][k0] += pick(dp, i - 2, j - 1, k0 - 1);
                dp[i][j][k0] += pick(dp, i - 1, j - 2, k0 - 1);
            }
        }
    }
    return dp[0][0][k];
}

private static int pick(int[][][] dp, int x, int y, int k) {
    if (x < 0 || x > 9 || y < 0 || y > 8) {
        return 0;
    }
    return dp[x][y][k];
}

题目9：咖啡杯问题——咖啡杯变干净最短时间

给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间
给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡
只有一台洗咖啡杯机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯
每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发
假设所有人拿到咖啡之后立刻喝干净，
返回从开始等到所有咖啡机变干净的最短时间
三个参数：int[] arr、intN，int a、int b

// 验证的方法
// 彻底的暴力
// 很慢但是绝对正确
public static int right(int[] arr, int n, int a, int b) {
    int[] times = new int[arr.length];
    int[] drink = new int[n];
    return forceMake(arr, times, 0, drink, n, a, b);
}

// 每个人暴力尝试用每一个咖啡机给自己做咖啡
public static int forceMake(int[] arr, int[] times, int kth, int[] drink, int n, int a, int b) {
    if (kth == n) {
        int[] drinkSorted = Arrays.copyOf(drink, kth);
        Arrays.sort(drinkSorted);
        return forceWash(drinkSorted, a, b, 0, 0, 0);
    }
    int time = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length; i++) {
        // 当前号咖啡机
        int work = arr[i];
        // 当前咖啡机可用时间
        int pre = times[i];
        // 当前人用，当前咖啡机喝完咖啡的时间
        drink[kth] = pre + work;
        // 当前咖啡机可用时间
        times[i] = pre + work;
        // 最短时间
        time = Math.min(time, forceMake(arr, times, kth + 1, drink, n, a, b));
        // 清空现场，当前人用下一个咖啡机
        drink[kth] = 0;
        times[i] = pre;
    }
    return time;
}

/**
 * 返回从开始等到所有咖啡机变干净的最短时间
 *
 * @param arr 泡咖啡机arr[i] ，arr[i]表示i号咖啡机泡咖啡需要arr[i]的时间
 * @param n   n个人准备泡咖啡
 * @param a   洗咖啡杯机洗干净一个杯子的时间
 * @param b   自然挥发干净的时间
 * @return 返回所有人从泡咖啡到咖啡杯变干净的最短时间
 */
public static int leastTime1(int[] arr, int n, int a, int b) {
    // 过滤无效参数
    if (arr == null || arr.length == 0 || n == 0 || a < 0 || b < 0) {
        return -1;
    }
    // 每个人最快喝完咖啡的时间点
    int[] drinkUpTime = leastMakeCoffeeTime(arr, n);
    return leastWashTime(drinkUpTime, a, b, 0, 0);
}

/**
 * 返回每个人喝完咖啡最短的的时间点，也就是每个人杯子可以洗或者挥发开始的时间点
 *
 * @param arr 咖啡机
 * @param n   n个人
 * @return 所有人都喝完咖啡的时间点
 */
private static int[] leastMakeCoffeeTime(int[] arr, int n) {

    // 按咖啡机可用时间与花费时间 组织小根堆
    PriorityQueue<CoffeeMachine> coffeeMachineHeap = new PriorityQueue<>(Comparator.comparingInt(c -> (c.availableTime + c.costTime)));
    // 初始化咖啡机，可用时间都为0时刻，放入小根堆
    for (int j : arr) {
        coffeeMachineHeap.add(new CoffeeMachine(0, j));
    }

    // 每个人喝完咖啡的时间点，也就是杯子可以洗的时间
    int[] drinkUpTime = new int[n];

    for (int i = 0; i < n; i++) {
        CoffeeMachine curCoffeeMachine = coffeeMachineHeap.poll();
        // 当前咖啡机下次可用时间点是开始可用时间点加上泡完一杯咖啡的时间
        assert curCoffeeMachine != null;
        curCoffeeMachine.availableTime += curCoffeeMachine.costTime;
        // 喝咖啡时间忽略，则一个人喝完一杯咖啡就是当前咖啡机可用时间点+泡完咖啡的时间
        drinkUpTime[i] = curCoffeeMachine.availableTime;
        coffeeMachineHeap.add(curCoffeeMachine);
    }
    return drinkUpTime;
}

/**
 * 泡咖啡机
 */
private static class CoffeeMachine {
    /**
     * 咖啡机可用时间
     */
    int availableTime;
    /**
     * 泡咖啡花费时间
     */
    int costTime;

    public CoffeeMachine(int availableTime, int costTime) {
        this.availableTime = availableTime;
        this.costTime = costTime;
    }
}

/**
 * @param drinkUpTime        所有人喝完咖啡的时间点，即时每个人可以洗杯子或挥发杯子的时间点
 * @param washCostTime       洗咖啡机洗杯子花费时间
 * @param volatilizeCostTime 自然挥发花费时间
 * @param index              当前下标
 * @param availableTime      洗咖啡机可用时间
 * @return 所有杯子变干净最短时间
 */
private static int leastWashTime(int[] drinkUpTime, int washCostTime, int volatilizeCostTime, int index, int availableTime) {
    // 已经没有杯子要处理
    if (index == drinkUpTime.length) {
        return 0;
    }
    //可能性1：当前杯子用洗

    // 当前杯子洗完的时间点，等于可以洗的时间点+洗杯子花费时间
    // 可以洗的时间点：①杯子可以洗，单洗咖啡机不可用，需要等到咖啡机可用时间点开始;②咖啡机可用，但杯子还没喝完，需要等到杯子喝完开始
    int beCleanTime1 = Math.max(drinkUpTime[index], availableTime) + washCostTime;
    // 剩余杯子变干净的时间点
    int restCleanTime1 = leastWashTime(drinkUpTime, washCostTime, volatilizeCostTime, index + 1, beCleanTime1);
    // 所有杯子变干净的最短时间点
    int leastCostTime1 = Math.max(beCleanTime1, restCleanTime1);

    //可能性2：当前杯子用挥发
    int beCleanTime2 = drinkUpTime[index] + volatilizeCostTime;
    int restCleanTime2 = leastWashTime(drinkUpTime, washCostTime, volatilizeCostTime, index + 1, availableTime);
    int leastCostTime2 = Math.max(beCleanTime2, restCleanTime2);
    return Math.min(leastCostTime1, leastCostTime2);
}

// 进行动态优化

public static int leastTime2(int[] arr, int n, int a, int b) {
    // 过滤无效参数
    if (arr == null || arr.length == 0 || n == 0 || a < 0 || b < 0) {
        return -1;
    }
    // 每个人最快喝完咖啡的时间点
    int[] drinkUpTime = leastMakeCoffeeTime(arr, n);

    return leastWashTimeDp(drinkUpTime, a, b);
}

/**
 * 返回每个人喝完咖啡最短的的时间点，也就是每个人杯子可以洗或者挥发开始的时间点
 *
 * @param arr 咖啡机
 * @param n   n个人
 * @return 所有人都喝完咖啡的时间点
 */
private static int[] leastMakeCoffeeTime(int[] arr, int n) {

    // 按咖啡机可用时间与花费时间 组织小根堆
    PriorityQueue<CoffeeMachine> coffeeMachineHeap = new PriorityQueue<>(Comparator.comparingInt(c -> (c.availableTime + c.costTime)));
    // 初始化咖啡机，可用时间都为0时刻，放入小根堆
    for (int j : arr) {
        coffeeMachineHeap.add(new CoffeeMachine(0, j));
    }

    // 每个人喝完咖啡的时间点，也就是杯子可以洗的时间
    int[] drinkUpTime = new int[n];

    for (int i = 0; i < n; i++) {
        CoffeeMachine curCoffeeMachine = coffeeMachineHeap.poll();
        // 当前咖啡机下次可用时间点是开始可用时间点加上泡完一杯咖啡的时间
        assert curCoffeeMachine != null;
        curCoffeeMachine.availableTime += curCoffeeMachine.costTime;
        // 喝咖啡时间忽略，则一个人喝完一杯咖啡就是当前咖啡机可用时间点+泡完咖啡的时间
        drinkUpTime[i] = curCoffeeMachine.availableTime;
        coffeeMachineHeap.add(curCoffeeMachine);
    }
    return drinkUpTime;
}

/**
 * 泡咖啡机
 */
private static class CoffeeMachine {
    /**
     * 咖啡机可用时间
     */
    int availableTime;
    /**
     * 泡咖啡花费时间
     */
    int costTime;

    public CoffeeMachine(int availableTime, int costTime) {
        this.availableTime = availableTime;
        this.costTime = costTime;
    }
}
private static int leastWashTimeDp(int[] drinkUpTime, int washCostTime, int volatilizeCostTime) {
    // 要洗的杯子的数量
    int n = drinkUpTime.length;
    // 洗咖啡机最晚可用时间
    int maxAvailableTime = 0;
    for (int j : drinkUpTime) {
        maxAvailableTime = Math.max(maxAvailableTime, j) + washCostTime;
    }
    int[][] dp = new int[n + 1][maxAvailableTime + 1];

    for (int index = n - 1; index >= 0; index--) {
        for (int curAvailableTime = 0; curAvailableTime <= maxAvailableTime; curAvailableTime++) {
            //可能性1：当前杯子用洗
            int beCleanTime1 = Math.max(drinkUpTime[index], curAvailableTime) + washCostTime;
            if (beCleanTime1 > maxAvailableTime) {
                break;
            }
            int restCleanTime1 = dp[index + 1][beCleanTime1];
            int leastCostTime1 = Math.max(beCleanTime1, restCleanTime1);

            //可能性2：当前杯子用挥发
            int beCleanTime2 = drinkUpTime[index] + volatilizeCostTime;
            int restCleanTime2 = dp[index + 1][curAvailableTime];
            int leastCostTime2 = Math.max(beCleanTime2, restCleanTime2);
            dp[index][curAvailableTime] = Math.min(leastCostTime1, leastCostTime2);
        }
    }
    return dp[0][0];
}

第21节.pptx

题目10：最小距离累加和

给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角。
沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和
返回最小距离累加和
（从左向右尝试模型）

//给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角
//沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和
//返回最小距离累加和


public static int miniPathSum1(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
        return -1;
    }
    return process1(matrix, matrix.length - 1, matrix[0].length - 1, 0, 0);
}


/**
 * 从当前位置matrix[i][j],到右下角matrix[x][y]的最短距离累加和
 *
 * @param matrix 二维数组
 * @param i      当前行
 * @param j      当前列
 * @param x      最后一行
 * @param y      最后一列
 * @return 最短距离累加和
 */
private static int process1(int[][] matrix, int x, int y, int i, int j) {
    if (i == x && j == y) {
        return matrix[x][y];
    }
    if (i == x && j < y) {
        return process1(matrix, x, y, i, j + 1) + matrix[i][j];
    }
    if (j == y && i < x) {
        return process1(matrix, x, y, i + 1, j) + matrix[i][j];
    }
    return matrix[i][j] + Math.min(process1(matrix, x, y, i, j + 1), process1(matrix, x, y, i + 1, j));
}


//给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角
//沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和
//返回最小距离累加和


public static int miniPathSum2(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
        return -1;
    }
    return process2(matrix, matrix.length - 1, matrix[0].length - 1);
}


/**
 * 从当前位置matrix[0][0],到matrix[x][y]的最短距离累加和
 *
 * @param matrix 二维数组
 * @param x      最后一行
 * @param y      最后一列
 * @return 最短距离累加和
 */
private static int process2(int[][] matrix, int x, int y) {
    if (x == 0 && y == 0) {
        return matrix[0][0];
    }
    if (x == 0) {
        return matrix[0][y] + process2(matrix, 0, y - 1);
    }
    if (y == 0) {
        return matrix[x][0] + process2(matrix, x - 1, 0);
    }

    return matrix[x][y] + Math.min(process2(matrix, x, y - 1), process2(matrix, x - 1, y));
}

// 第一种暴力递归和第二种暴力递归其实是一类，从左向右尝试模型，把其中一种改为动态规划

public static int miniPathSum3(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
        return -1;
    }
    int n = matrix.length;
    int m = matrix[0].length;
    int[][] dp = new int[n][m];
    dp[0][0] = matrix[0][0];
    for (int j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + matrix[0][j];
    }
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + matrix[i][0];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
        }
    }

    return dp[n - 1][m - 1];
}

根据dp表位置依赖关系，可以看推出空间压缩。

//对于以上递归，dp表可以进行压缩
public static int miniPathSum4(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
        return -1;
    }
    int n = matrix.length;
    int m = matrix[0].length;
    int len = Math.min(m, n);
    int[] dp = new int[len];
    dp[0] = matrix[0][0];
    if (len == m) {
        for (int j = 1; j < m; j++) {
            dp[j] = dp[j - 1] + matrix[0][j];
        }
        for (int i = 1; i < n; i++) {
            dp[0] += matrix[i][0];
            for (int j = 1; j < m; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + matrix[i][j];
            }
        }
    } else {
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] + matrix[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0] += matrix[0][j];
            for (int i = 1; i < m; i++) {
                dp[i] = Math.min(dp[i], dp[i - 1]) + matrix[i][i];
            }
        }
    }
    return dp[len - 1];
}

题目11：货币问题1——每张货币不同

arr是货币数组，其中的值都是正数。再给定一个正数aim。每个值都认为是一张货币，即便是值相同的货币也认为每一张都是不同的，返回组成aim的方法数
例如：arr={1,1,1}，aim=2，第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2，一共就3种方法，所以返回3

//arr是货币数组，其中的值都是正数。再给定一个正数aim。
//每个值都认为是一张货币，
//即便是值相同的货币也认为每一张都是不同的，
//返回组成aim的方法数
//例如：arr = {1,1,1}，aim = 2
//第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2
//一共就3种方法，所以返回3

public static int differentWays(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return -1;
    }
    if (aim == 0) {
        return 1;
    }
    return process(arr, aim, 0);
}

private static int process(int[] arr, int rest, int i) {
    if (rest < 0) {
        return 0;
    }
    if (i == arr.length) {
        return rest == 0 ? 1 : 0;
    } else {
        int p1 = process(arr, rest, i + 1);
        int p2 = 0;
        p2 = process(arr, rest - arr[i], i + 1);
        return p1 + p2;
    }
}

// 对暴力递归改动态规划

public static int differentWays2(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return -1;
    }
    if (aim == 0) {
        return 1;
    }

    int n = arr.length;
    int[][] dp = new int[n + 1][aim + 1];
    dp[n][0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = aim; j >= 0; j--) {
            dp[i][j] = dp[i + 1][j] + (j - arr[i] >= 0 ? dp[i + 1][j - arr[i]] : 0);
        }
    }

    return dp[0][aim];
}

// 以上递归压缩空间

public static int differentWays3(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return -1;
    }
    if (aim == 0) {
        return 1;
    }

    int n = arr.length;
    int[] dp = new int[aim + 1];
    dp[0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = aim; j >= 0; j--) {
            dp[j] += (j - arr[i] >= 0 ? dp[j - arr[i]] : 0);
        }
    }
    return dp[aim];
}

题目12：货币问题2——面值没有重复，每种面试无数张

arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。返回组成aim的方法数
例如：arr={1,2}，aim=4方法如下：1+1+1+1、1+1+2、2+2，一共就3种方法，所以返回3


//arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。返回组成aim的方法数
//例如：arr={1,2}，aim=4方法如下：1+1+1+1、1+1+2、2+2，一共就3种方法，所以返回3

public static int differentWays1(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    if (aim == 0) {
        return 1;
    }
    return process(arr, aim, 0);
}

private static int process(int[] arr, int rest, int index) {

    if (index == arr.length) {
        return rest == 0 ? 1 : 0;
    }
    int ans = 0;
    for (int i = 0; rest - arr[index] * i >= 0; i++) {
        ans += process(arr, rest - arr[index] * i, index + 1);
    }
    return ans;
}

// 暴力递归改动态规划


public static int differentWays2(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    if (aim == 0) {
        return 1;
    }
    int n = arr.length;
    int[][] dp = new int[n + 1][aim + 1];
    dp[n][0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = aim; j >= 0; j--) {
            for (int k = 0; j - arr[i] * k >= 0; k++) {
                dp[i][j] += dp[i + 1][j - arr[i] * k];
            }
        }
    }
    return dp[0][aim];
}

/*
对上面递归 每个位置的枚举行为进行分析
int m = arr[i],j-(k+1)m<0,则：
dp[i][j] = dp[i+1][j]+dp[i+1][j-m]+dp[i+1][j-2m]+dp[i+1][j-3m]+……+dp[i+1][j-km]

dp[i][j-m] = dp[i+1][j-m]+dp[i+1][j-2m]+dp[i+1][j-3m]+……+dp[i+1][j-km]

因此，dp[i][j]的枚举行为可以被dp[i][j-m]代替  =》 dp[i][j]=dp[i+1][j]+dp[i][j-m]
*/

public static int differentWays3(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        if (aim == 0) {
            return 1;
        }
        int n = arr.length;
        int[][] dp = new int[n + 1][aim + 1];
        dp[n][0] = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= aim; j++) {
                dp[i][j] += dp[i + 1][j];
                if (j - arr[i] >= 0) {
                    dp[i][j] += dp[i][j - arr[i]];
                }
            }
        }
        return dp[0][aim];
    }
}

题目13：货币问题3——面值相同认为是一张，有限张数货币

arr是货币数组，其中的值都是正数。再给定一个正数aim。每个值都认为是一张货币，认为值相同的货币没有任何不同，返回组成aim的方法数
例如：arr={1,2,1,1,2,1,2}，aim=4，方法：1+1+1+1、1+1+2、2+2一共就3种方法，所以返回3

public static int differentWays1(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    if (aim == 0) {
        return 1;
    }

    Info info = getInfo(arr);
    return process(info.coins, info.count, 0, aim);
}

private static int process(int[] vales, int[] count, int index, int rest) {
    if (index == vales.length) {
        return rest == 0 ? 1 : 0;
    }
    int ans = 0;
    for (int i = 0; (i <= count[index]) && (rest - vales[index] * i >= 0); i++) {
        ans += process(vales, count, index + 1, rest - vales[index] * i);
    }
    return ans;
}


// 暴力递归改动态规划

public static int differentWays2(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    if (aim == 0) {
        return 1;
    }
    Info info = getInfo(arr);
    int[] coins = info.coins;
    int[] counts = info.count;
    int n = counts.length;
    int[][] dp = new int[n + 1][aim + 1];
    dp[n][0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = aim; j >= 0; j--) {
            for (int k = 0; k <= counts[i] && (j - coins[i] * k >= 0); k++) {
                dp[i][j] += dp[i + 1][j - coins[i] * k];
            }
        }

    }
    return dp[0][aim];
}


/*
对动态规划表，每个位置的枚举行为进行优化
coins[i]=m,count[i] = k,j-km>=0
dp[i][j] = dp[i + 1][j]+dp[i+1][j-m]+dp[i+1][j-2m]+……+dp[i+1][j-km]

dp[i][j-m] = dp[i+1][j-m]+dp[i+1][j-2m]+……+dp[i+1][j-m-km]

==> dp[i][j] = dp[i+1][j]+dp[i][j-m]-dp[i+1][j-m-km]
*/


public static int differentWays3(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    if (aim == 0) {
        return 1;
    }
    Info info = getInfo(arr);
    int[] coins = info.coins;
    int[] count = info.count;
    int n = count.length;
    int[][] dp = new int[n + 1][aim + 1];
    dp[n][0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= aim; j++) {
            dp[i][j] = dp[i + 1][j];
            if (j - coins[i] >= 0) {
                dp[i][j] += dp[i][j - coins[i]];
            }
            if (j - (coins[i] * (count[i] + 1)) >= 0) {
                dp[i][j] -= dp[i + 1][j - coins[i] * (count[i] + 1)];
            }
        }
    }

    return dp[0][aim];
}

题目14：Bob生存概率（类似题目8,象棋跳马问题）

给定5个参数，N，M，row，col，k
表示在NM的区域上，醉汉Bob初始在(row,col)位置
Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位
任何时候Bob只要离开NM的区域，就直接死亡
返回k步之后，Bob还在N*M的区域的概率


public static double livePossibility1(int n, int m, int row, int col, int k) {
    return process(n, m, row, col, k) / Math.pow(4, k);
}

private static long process(int n, int m, int x, int y, int rest) {
    if (x < 0 || x == n || y < 0 || y == m) {
        return 0;
    }
    if (rest == 0) {
        return 1L;
    }
    return process(n, m, x + 1, y, rest - 1) + process(n, m, x - 1, y, rest - 1) + process(n, m, x, y + 1, rest - 1) + process(n, m, x, y - 1, rest - 1);
}


public static double livePossibility2(int n, int m, int row, int col, int k) {
    long[][][] dp = new long[n][m][k + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[i][j][0] = 1L;
        }
    }
    for (int h = 1; h <= k; h++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j][h] = pick(dp, n, m, i - 1, j, h - 1);
                dp[i][j][h] += pick(dp, n, m, i + 1, j, h - 1);
                dp[i][j][h] += pick(dp, n, m, i, j - 1, h - 1);
                dp[i][j][h] += pick(dp, n, m, i, j + 1, h - 1);
            }
        }
    }
    return (double) dp[row][col][k] / Math.pow(4, k);
}

public static long pick(long[][][] dp, int n, int m, int r, int c, int rest) {
    if (r < 0 || r == n || c < 0 || c == m) {
        return 0;
    }
    return dp[r][c][rest];
}

第22节.pptx

题目15：怪兽死亡概率问题

给定3个参数，N，M，K，怪兽有N滴血，等着英雄来砍自己，英雄每一次打击，都会让怪兽流失[0~M]的血量
到底流失多少？每一次在[0~M]上等概率的获得一个值，求K次打击之后，英雄把怪兽砍死的概率


/**
 * k次打击后，怪兽死亡的概率
 *
 * @param n 怪兽hp
 * @param m 最大伤害，伤害0~m
 * @param k k次攻击
 * @return 怪兽死亡概率
 */
public static double possibility1(int n, int m, int k) {
    if (n < 1 || m < 1 || k < 1) {
        return 0;
    }
    return process(n, m, k) / Math.pow(m + 1, k);
}

/**
 * 怪兽当前hp血量，剩余rest攻击次数，每次攻击伤害0~m,返回hp<=0的次数
 */
public static long process(int hp, int m, int rest) {
    if (rest == 0) {
        return hp == 0 ? 1L : 0;
    }
    if (hp == 0) {
        return (long) Math.pow(m + 1, rest);
    }

    long ans = 0;
    for (int i = 0; i <= m; i++) {
        ans += process(Math.max(hp - i, 0), m, rest - 1);
    }
    return ans;
}

// 对以上暴力递归改动态规划

public static double possibility2(int n, int m, int k) {
    if (n < 1 || m < 1 || k < 1) {
        return 0;
    }

    long[][] dp = new long[n + 1][k + 1];
    dp[0][0] = 1;

    for (int i = 1; i <= k; i++) {
        dp[0][i] = (long) Math.pow(m + 1, i);
    }

    for (int hp = 1; hp <= n; hp++) {
        for (int rest = 1; rest <= k; rest++) {
            for (int i = 0; i <= m; i++) {
                dp[hp][rest] += dp[Math.max(hp - i, 0)][rest - 1];
            }
        }
    }

    return dp[n][k] / Math.pow(m + 1, k);
}

/* 以上dp表每个表格存在枚举行为，如何优化？找规律

    dp[i][j] = dp[i][j-1]+dp[i-1][j-1]+dp[i-1][j-1]+……+dp[i-m][j-1]

    dp[i-1][j] = dp[i-1][j-1]+dp[i-2][j-1]+dp[i-3][j-1]+……+dp[i-m][j-1]+dp[i-m-1][j-1]

    dp[i][j] = dp[i][j-1]+dp[i-1][j]+dp[i-m][j-1]-dp[i-m-1][j-1]
 */


public static double possibility3(int n, int m, int k) {
    if (n < 1 || m < 1 || k < 1) {
        return 0;
    }

    long[][] dp = new long[n + 1][k + 1];
    dp[0][0] = 1;

    for (int i = 1; i <= k; i++) {
        dp[0][i] = (long) Math.pow(m + 1, i);
    }

    for (int hp = 1; hp <= n; hp++) {
        for (int rest = 1; rest <= k; rest++) {
            dp[hp][rest] = dp[hp][rest - 1] + dp[hp - 1][rest] - dp[Math.max(hp - m - 1, 0)][rest - 1];
        }
    }

    return dp[n][k] / Math.pow(m + 1, k);
}

题目16：货币问题4——面值不重复，无限张，返回最少货币数

arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。返回组成aim的最少货币数。

//arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。
// 返回组成aim的最少货币数。

public static int minCoins1(int[] arr, int aim) {
    if (aim == 0) {
        return 0;
    }
    return process(arr, aim, 0);
}


/**
 * 当前选择第i张货币，剩余目标金额restAim,返回需要的最少货币数
 */
private static int process(int[] arr, int restAim, int index) {
    // 已经没有货币可以选，如果此时剩余目标金额为0，则需要0张，如果不为0，返回最大int值
    if (index == arr.length) {
        return restAim == 0 ? 0 : Integer.MAX_VALUE;
    }
    if (restAim == 0) {
        return 0;
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; restAim - arr[index] * i >= 0; i++) {
        int left = process(arr, restAim - arr[index] * i, index + 1);
        if (left != Integer.MAX_VALUE) {
            ans = Math.min(ans, i + left);
        }
    }
    return ans;
}

// 对以上暴力递归改动态规划


public static int minCoins2(int[] arr, int aim) {
    if (aim == 0) {
        return 0;
    }

    int n = arr.length;
    int[][] dp = new int[n + 1][aim + 1];
    for (int i = 1; i <= aim; i++) {
        dp[n][i] = Integer.MAX_VALUE;
    }
    for (int index = n - 1; index >= 0; index--) {
        for (int restAim = 0; restAim <= aim; restAim++) {
            int ans = Integer.MAX_VALUE;
            for (int i = 0; restAim - arr[index] * i >= 0; i++) {
                if (dp[index + 1][restAim - arr[index] * i] != Integer.MAX_VALUE) {
                    ans = Math.min(ans, i + dp[index + 1][restAim - arr[index] * i]);
                }
            }
            dp[index][restAim] = ans;
        }
    }
    return dp[0][aim];
}

/*
 * 对以上dp中的枚举行为进行优化
 *
 * j-(n+1)arr[i]<0
 * 0<=x<=n
 * 需满足：dp[i + 1][j - arr[i] * x] != Integer.MAX_VALUE
 *
 * Math.min() = a
 *
 * dp[i][j] = Math.min(Integer.MAX_VALUE，dp[i+1][j]，dp[i+1][j-arr[i]]+1,dp[i+1][j-2*arr[i]]+2,……,dp[i+1][j-n*arr[i]]+n))
 *
 *
 *
 *
 * ap[i][j-arr[i]]!=Integer.MAX_VALUE
 *
 * dp[i][j-arr[i]) = Math.min(Integer.MAX_VALUE，dp[i+1][j-arr[i]) , dp[i+1][j-2arr[i]]+1,  dp[i+1][j-3*arr[i]]+2  ,……,  dp[i+1][j-n*arr[i]]+n-1))
 *
 * ==》dp[i][j-arr[i])+1 = Math.min(Integer.MAX_VALUE，dp[i+1][j-arr[i])+1 , dp[i+1][j-2arr[i]]+2,  dp[i+1][j-3*arr[i]]+3  ,……,  dp[i+1][j-n*arr[i]]+n))
 *
 *
 * ==》dp[i][j] = Math.min(Integer.MAX_VALUE,dp[i+1][j],dp[i][j-arr[i])+1)
 *
 *
 *
 * */

public static int minCoins3(int[] arr, int aim) {
    if (aim == 0) {
        return 0;
    }

    int n = arr.length;
    int[][] dp = new int[n + 1][aim + 1];
    for (int i = 1; i <= aim; i++) {
        dp[n][i] = Integer.MAX_VALUE;
    }
    for (int index = n - 1; index >= 0; index--) {
        for (int restAim = 0; restAim <= aim; restAim++) {
            dp[index][restAim] = dp[index + 1][restAim];
            if (restAim - arr[index] >= 0 && dp[index][restAim - arr[index]] != Integer.MAX_VALUE) {
                dp[index][restAim] = Math.min(dp[index][restAim], 1 + dp[index][restAim - arr[index]]);
            }
        }
    }
    return dp[0][aim];
}

题目17：数字分裂

给定一个正数n，求n的裂开方法数，规定：后面的数不能比前面的数小
比如4的裂开方法有：1+1+1+1、1+1+2、1+3、2+2、4，5种，所以返回5

public static int splitNumber(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return process(1, n);
}

private static int process(int pre, int rest) {
    if (rest == 0) {
        return 1;
    } else {
        int ans = 0;
        for (int i = pre; i <= rest; i++) {
            ans += process(i, rest - i);
        }
        return ans;
    }
}

// 以上递归改dp

public static int splitNumber2(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }

    int[][] dp = new int[n + 1][n + 1];
    for (int i = 1; i < n; i++) {
        dp[i][0] = 1;
        dp[i][i] = 1;
    }
    for (int pre = n - 1; pre > 0; pre--) {
        for (int rest = pre + 1; rest <= n; rest++) {
            int ans = 0;
            for (int i = pre; i <= rest; i++) {
                ans += dp[i][rest - i];
            }
            dp[pre][rest] = ans;
        }

    }
    return process(1, n);
}

// 以上递归枚举行为进行优化

public static int splitNumber3(int n) {
    if (n < 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    int[][] dp = new int[n + 1][n + 1];
    for (int pre = 1; pre <= n; pre++) {
        dp[pre][0] = 1;
        dp[pre][pre] = 1;
    }
    for (int pre = n - 1; pre >= 1; pre--) {
        for (int rest = pre + 1; rest <= n; rest++) {
            dp[pre][rest] = dp[pre + 1][rest];
            dp[pre][rest] += dp[pre][rest - pre];
        }
    }
    return dp[1][n];
}

第23节.pptx

题目18：最接近的情况下，较小集合累加和

给定一个正数数组arr，请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近
返回：最接近的情况下，较小集合的累加和

//给定一个正数数组arr，请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近
//返回：最接近的情况下，较小集合的累加和


public static int closedArrSum(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }

    int sum = 0;
    for (int num : arr) {
        sum += num;
    }

    int target = sum / 2;

    return process(arr, 0, target);
}

private static int process(int[] arr, int index, int target) {
    if (target == 0) {
        return 0;
    } else {
        if (index == arr.length) {
            return 0;
        } else {
            int p1 = process(arr, index + 1, target);
            int p2 = 0;
            if (target - arr[index] >= 0) {
                p2 = arr[index] + process(arr, index + 1, target - arr[index]);
            }
            return Math.max(p1, p2);
        }
    }
}

// 以上递归改动态规划


public static int closedArrSum2(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }

    int sum = 0;
    for (int num : arr) {
        sum += num;
    }

    int target = sum / 2;

    int n = arr.length;
    int[][] dp = new int[n + 1][target + 1];

    for (int i = n - 1; i >= 0; i--) {
        for (int j = target; j >= 0; j--) {
            int p1 = dp[i + 1][j];
            int p2 = 0;
            if (j - arr[i] >= 0) {
                p2 = arr[i] + dp[i + 1][j - arr[i]];
            }
            dp[i][j] = Math.max(p1, p2);
        }
    }
    return dp[0][target];
}

题目19：集合书面一样多或相差1，最接近的情况下，较小集合累加和

给定一个正数数组arr，请把arr中所有的数分成两个集合，如果arr长度为偶数，两个集合包含数的个数要一样多，如果arr长度为奇数，两个集合包含数的个数必须只差一个，请尽量让两个集合的累加和接近
返回：最接近的情况下，较小集合的累加和


public static int closedSum(int[] arr) {

    if (arr == null || arr.length < 2) {
        return 0;
    }

    int sum = 0;
    for (int num : arr) {
        sum += num;
    }
    int target = sum / 2;

    if ((arr.length & 1) == 0) {
        return process(arr, 0, arr.length / 2, target);
    } else {
        return Math.max(process(arr, 0, arr.length / 2, target), process(arr, 0, arr.length / 2 + 1, target));
    }

}

private static int process(int[] arr, int i, int picks, int target) {
    if (i == arr.length) {
        return picks == 0 ? 0 : -1;
    } else {
        int p1 = process(arr, i + 1, picks, target);
        // 就是要使用arr[i]这个数
        int p2 = -1;
        int next = -1;
        if (arr[i] <= target) {
            next = process(arr, i + 1, picks - 1, target - arr[i]);
        }
        if (next != -1) {
            p2 = arr[i] + next;
        }
        return Math.max(p1, p2);
    }

}

// 改动态规划
public static int closedSum2(int[] arr) {

    if (arr == null || arr.length < 2) {
        return 0;
    }

    int sum = 0;
    for (int num : arr) {
        sum += num;
    }
    int target = sum / 2;
    int n = arr.length;
    int picks = (n + 1) / 2;
    int[][][] dp = new int[n + 1][picks + 1][target + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= picks; j++) {
            for (int k = 0; k <= target; k++) {
                dp[i][j][k] = -1;
            }
        }
    }

    for (int rest = 0; rest <= target; rest++) {
        dp[n][0][rest] = 0;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= picks; j++) {
            for (int k = 0; k <= target; k++) {
                int p1 = dp[i + 1][j][k];
                // 就是要使用arr[i]这个数
                int p2 = -1;
                int next = -1;
                if (j - 1 >= 0 && arr[i] <= k) {
                    next = dp[i + 1][j - 1][k - arr[i]];
                }
                if (next != -1) {
                    p2 = arr[i] + next;
                }
                dp[i][j][k] = Math.max(p1, p2);
            }
        }
    }


    if ((arr.length & 1) == 0) {
        return dp[0][arr.length / 2][target];
    } else {
        return Math.max(dp[0][arr.length / 2][target], dp[0][arr.length / 2 + 1][target]);
    }
}

题目20：N皇后问题

N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列， 也不在同一条斜线上
给定一个整数n，返回n皇后的摆法有多少种。
例：n=1，返回1，n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0，n=8，返回92


public static int num(int n) {
    if (n < 1) {
        return 0;
    }
    int[] record = new int[n];
    return precess(0, record, n);
}

private static int precess(int i, int[] record, int n) {
    if (i == n) {
        return 1;
    }
    int ans = 0;
    for (int j = 0; j < n; j++) {
        if (valid(record, i, j)) {
            record[i] = j;
            ans += precess(i + 1, record, n);
        }
    }
    return ans;
}

private static boolean valid(int[] record, int i, int j) {
    for (int k = 0; k < i; k++) {
        if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
            return false;
        }
    }
    return true;
}


// 请不要超过32皇后问题
public static int num2(int n) {
    if (n < 1 || n > 32) {
        return 0;
    }
    // 如果你是13皇后问题，limit 最右13个1，其他都是0
    int limit = n == 32 ? -1 : (1 << n) - 1;
    return process2(limit, 0, 0, 0);
}

// 7皇后问题
// limit : 0....0 1 1 1 1 1 1 1
// 之前皇后的列影响：colLim
// 之前皇后的左下对角线影响：leftDiaLim
// 之前皇后的右下对角线影响：rightDiaLim
public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
    if (colLim == limit) {
        return 1;
    }
    // pos中所有是1的位置，是你可以去尝试皇后的位置
    int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
    int mostRightOne = 0;
    int res = 0;
    while (pos != 0) {
        mostRightOne = pos & (~pos + 1);
        pos = pos - mostRightOne;
        res += process2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1,
                (rightDiaLim | mostRightOne) >>> 1);
    }
    return res;
}