一个大问题可以分解为许多小问题，小问题一步步的推导出大问题，且小问题会有很多重复的。

  1. DP问题通常可以先使用暴力递归的形式求解。
  2. 在暴力递归的规程中，对小问题的答案进行缓存，防止重复计算，成为记忆化搜索
  3. 根据暴力递归的控制参数决定dp数组含义，bad case 观察dp数组转移规律，使用具体例子来观察规律
  4. 构建dp数组，首先根据bad case构建已知的位置，其他位置转移时根据暴力递归的逻辑，将递归改为从dp数组中拿值

机器人路径

给定一个n，范围为0 ~ n-1，机器人一开始处于start位置，经过step步到达end位置的方法有几种？

  1. 暴力递归尝试

首先定义递归函数，当前处于cur位置，如果能经过step步到达end，则对count进行自增。
如果cur在两端，则只能向另一侧移动，否则可以向两边移动。

  1.     public void testRobotTrace() {
  2.         int i = robotTrace(6, 2, 4, 4);
  3.         System.out.println(i);
  4.     }
  6.     /**
  7.      * 范围0 ~ n-1, 从start开始走step步到达end的路径数
  8.      */
  9.     public int robotTrace(int n,int start,int step,int end){
  10.         int trace = trace(n, end, step, start);
  11.         System.out.println(trace == 4);
  12.         return trace;
  13.     }
  15.     /**
  16.      * @param cur 当前位置
  17.      * @return 方法数
  18.      */
  19.     private int trace(int n,int end,int step,int cur){
  20.         if (step == 0){
  21.             return cur == end ? 1 : 0;
  22.         }
  23.         // 左端点必须走右边
  24.         if (cur == 0){
  25.             return trace(n,end,step-1,1);
  26.         }else
  27.         // 右端点必须走左边
  28.         if (cur == n-1){
  29.             return trace(n,end,step-1,n-2);
  30.         }else {
  31.             int right = trace(n,end,step-1,cur+1);
  32.             int left = trace(n,end,step-1,cur-1);
  33.             return left + right;
  34.         }
  35.     }
  1. 分析包里递归是否包含重复子问题

我们举例n=6，start=2，end=4，step=4。
路径1：2-3-4-5-4
路径2：2-3-4-3-4
我们看到从4到达4，step=2时的子问题重复出现，因此可以使用缓存进行优化

  1. 基于缓存优化暴力递归子问题

cache数组为二维数组，cache[i][j]代表在i位置还剩j步能到达end的步数，初始的时候全部初始化为-1.
容量为n和step+1，因为我们的范围是0~n-1，step取值0~step

  1. public void testRobotTrace() {
  2.         int i = robotTrace(6, 2, 4, 4);
  3.         System.out.println(i);
  4.     }
  6.     /**
  7.      * 范围0 ~ n-1, 从start开始走step步到达end的路径数
  8.      */
  9.     public int robotTrace(int n, int start, int step, int end) {
  10.         int[][] cache = new int[n][step+1];
  11.         for (int i = 0; i < cache.length; i++) {
  12.             Arrays.fill(cache[i],-1);
  13.         }
  14.         int trace = traceCache(n, end, step, start,cache);
  15.         System.out.println(trace == 4);
  16.         return trace;
  17.     }
  19.     private int traceCache(int n, int end, int step, int cur, int[][] cache) {
  20.         if (cache[cur][step] >= 0) {
  21.             return cache[cur][step];
  22.         }
  23.         if (step == 0) {
  24.             int count = cur == end ? 1 : 0;
  25.             cache[cur][step] = count;
  26.             return count;
  27.         }
  28.         int count = 0;
  29.         if (cur == 0) {
  30.             count = trace(n, end, step - 1, 1);
  31.         } else if (cur == n - 1) {
  32.             count = trace(n, end, step - 1, n - 2);
  33.         } else {
  34.             int right = trace(n, end, step - 1, cur + 1);
  35.             int left = trace(n, end, step - 1, cur - 1);
  36.             count = left + right;
  37.         }
  38.         cache[cur][step] = count;
  39.         return count;
  40.     }
  1. cache数组规律查找，构建dp数组dp[cur][step]

举例n=6，start=2，end=4，step=4
首先根据bad case设置对应值

  1. if (step == 0) {
  2.    int count = cur == end ? 1 : 0;
  3.    cache[cur][step] = count;
  4.    return count;
  5. }
dp 0 1 2 3 4
0 0
1 0
2 0
3 0
4 1
5 0

然后根据我们的逻辑可以看出，转移过程是从step-1 到 step的，因此我们可以直接推出整个dp数组。

  1. int count = 0;
  2. if (cur == 0) {
  3.     count = trace(n, end, step - 1, 1);
  4. } else if (cur == n - 1) {
  5.     count = trace(n, end, step - 1, n - 2);
  6. } else {
  7.     int right = trace(n, end, step - 1, cur + 1);
  8.     int left = trace(n, end, step - 1, cur - 1);
  9.     count = left + right;
  10. }
  11. cache[cur][step] = count;
  12. return count;
dp 0 1 2 3 4
0 0 0 0 0 1
1 0 0 0 1 0
2 0 0 1 0 4
3 0 1 0 3 0
4 1 0 2 0 5
5 0 1 0 2 0 
  1. public int robotTraceDp(int n, int start, int step, int end) {
  2.         int[][] dp = new int[n][step+1];
  3.         dp[end][0] = 1;
  4.         for (int i = 1; i <= step; i++) {
  5.             dp[0][i] = dp[1][i-1];
  6.             for (int j = 1; j < n-1; j++) {
  7.                 dp[j][i] = dp[j+1][i-1] + dp[j-1][i-1];
  8.             }
  9.             dp[n-1][i] = dp[n-2][i-1];
  10.         }
  11.         return dp[start][step];
  12. }

我们返回值直接取我们的递归方法调用的形式，即返回dp[start][step]即可

游戏博弈

背包问题

有数组weight[]和数组value[],分别代表货物的重量和价值，现有容量为bag的背包，求背包能装货物的最大价值 ps: 0 < weight.length = value.length <1000 weight[i] >= 0 , value[i] >=0 bag >= 0

  1. 暴力递归尝试

朴素的自左向右/自顶向下的暴力递归方法，就是对条件数组进行遍历决策。背包问题只有两个决策，要或者不要，因此从左至右进行遍历货物选择要或者不要

  1. /**
  2.      *
  3.      * @param wight 货物重量数组
  4.      * @param value 货物价值数组
  5.      * @param bag 背包最大容量
  6.      * @return 背包能装货物的最大价值
  7.      */
  8.     public int maxValue(int[] wight, int[] value, int bag){
  9.         return maxValue(wight,value,0,bag);
  10.     }
  11.     /**
  12.      *
  13.      * @param wight 货物重量数组
  14.      * @param value 货物价值数组
  15.      * @param index 当前货物索引
  16.      * @param bag 背包最大容量
  17.      * @return 背包能装货物的最大价值
  18.      */
  19.     public int maxValue(int[] wight, int[] value, int index, int bag){
  20.         if (bag < 0){
  21.             return 0;
  22.         }
  23.         if (index == wight.length){
  24.             return 0;
  25.         }
  26.         // index货物不要
  27.         int v1 = maxValue(wight,value,index+1,bag);
  28.         // index货物要,但是不能超过背包容量
  29.         // 如果超过了背包容量，这个选择是非法的，所以只能选择不要
  30.         // 这里让v2==0，其实只要让v2<v1即可
  31.         int v2 = bag-wight[index] >= 0 ?
  32.                 value[index] + maxValue(wight, value, index+1, bag-wight[index])
  33.                 : 0;
  34.         // 选最大的
  35.         return Math.max(v1,v2);
  36.     }
  39.     public static void main(String[] args) {
  40.         Solution solution = new Solution();
  41.         int[] wight = {3,2,4,7};
  42.         int[] value = {5,6,3,19};
  43.         int bag = 11;
  44.         int ans = solution.maxValue(wight, value, bag);
  45.         System.out.println(ans == 25);
  46.     }
  1. 分析暴力递归重复子问题

我们观察到暴力递归的每次递归的控制参数是index和bag，即index和bag组成了一个个的子问题。
我们举例有wight=[4,5,9,1], bag = 12.
当选择了wight[0],wight[1],没有选择wight[2]时，有子问题index=3,bag = 3
当没有选择wight[0],wight[1],选择wight[2]时，有子问题index=3,bag = 3
即有重复子问题，可以使用缓存避免重复子问题求解。

  1. 基于缓存优化暴力递归

基于缓存优化的思路很简单，进入递归，通过bad case后，先看缓存中有没有，有直接返回。
没有缓存，计算出结果后，返回之前先存到缓存里。
这里缓存为了后续的方便dp数组创建，直接用数组了，单纯的缓存话由于bag可能很大，可以用map代替
cache缓存是个二维数组，行为index范围为[0,weight.length]，列为bag范围为[负数,bag]
因此cache的大小也可以为wight.length+1和bag+1
注意：wight.length+1貌似是可以替换为wight.length，因为在bad case里如果index == wight.length 会直接返回。这是正确的，这里定义为wight.length+1的目的是因为在递归的过程中，index是可以等于wight.length的，虽然在bad case里直接返回了，但是我们可以多定义一行以包含参数中出现的边界。后面可以看到多出一行后在找出dp数组的规律时更直观

  1. /**
  2.      *
  3.      * @param wight 货物重量数组
  4.      * @param value 货物价值数组
  5.      * @param bag 背包最大容量
  6.      * @return 背包能装货物的最大价值
  7.      */
  8.     public int maxValue(int[] wight, int[] value, int bag){
  9.         int[][] cache = new int[wight.length+1][bag+1];
  10.         for (int i = 0; i < cache.length; i++) {
  11.             Arrays.fill(cache[i],-1);
  12.         }
  13.         return maxValue(wight,value,0,bag,cache);
  14.     }
  15.     /**
  16.      *
  17.      * @param wight 货物重量数组
  18.      * @param value 货物价值数组
  19.      * @param index 当前货物索引
  20.      * @param bag 背包最大容量
  21.      * @return 背包能装货物的最大价值
  22.      */
  23.     public int maxValue(int[] wight, int[] value, int index, int bag, int[][] cache){
  24.         if (bag < 0){
  25.             return 0;
  26.         }
  27.         if (index == wight.length){
  28.             return 0;
  29.         }
  30.         if (cache[index][bag] >= 0){
  31.             return cache[index][bag];
  32.         }
  33.         // index货物不要
  34.         int v1 = maxValue(wight,value,index+1,bag,cache);
  35.         // index货物要,但是不能超过背包容量
  36.         // 如果超过了背包容量，这个选择是非法的，所以只能选择不要，这里让v2==0，后面选最大值自然选了v1
  37.         int v2 = bag-wight[index] >= 0 ?
  38.                 value[index] + maxValue(wight, value, index+1, bag-wight[index],cache)
  39.                 : 0;
  40.         // 选最大的
  41.         int ans = Math.max(v1,v2);
  42.         cache[index][bag] = ans;
  43.         return ans;
  44.     }
  46.     public static void main(String[] args) {
  47.         Solution solution = new Solution();
  48.         int[] wight = {3,2,4,7};
  49.         int[] value = {5,6,3,19};
  50.         int bag = 11;
  51.         int ans = solution.maxValue(wight, value, bag);
  52.         System.out.println(ans == 25);
  53.     }
  1. 根据cache数组的构建规则推导dp转移数组

其实cache数组就是dp数组，我们先根据一个实际的例子来看cache数组的规律，如下是cache数组，我们换个名字叫dp数组，根据主函数的调用可知我们的目标答案是dp[0][11]

  1. return maxValue(wight,value,0,bag,cache);
dp 0 1 2 3 4 5 6 7 8 9 10 11
0 ※
1
2
3
4 
  1. if (index == wight.length){return 0;}
dp 0 1 2 3 4 5 6 7 8 9 10 11
0
1
2
3
4 0 0 0 0 0 0 0 0 0 0 0 0 
  1. // index货物不要
  2. int v1 = maxValue(wight,value,index+1,bag,cache);
  3. // index货物要,但是不能超过背包容量
  4. // 如果超过了背包容量，这个选择是非法的，所以只能选择不要，这里让v2==0，后面选最大值自然选了v1
  5. int v2 = bag-wight[index] >= 0 ?
  6.         value[index] + maxValue(wight, value, index+1, bag-wight[index],cache)
  7.         : 0;
  8. // 选最大的
  9. int ans = Math.max(v1,v2);

从代码可以看出，index行的值是基于index+1行转移出来的，因此我们能够从index=4的值推出index=3，2，1，0的值，这个规律就是转移方程，因此从该规律我们可以直接构造dp数组，将递归过程直接换成从dp数组取值即可。

dp 0 1 2 3 4 5 6 7 8 9 10 11
0 0 0 6 6 6 11 11 19 19 25 25 25
1 0 0 6 6 6 6 9 19 19 25 25 25
2 0 0 0 0 3 3 3 19 19 19 19 22
3 0 0 0 0 0 0 0 19 19 19 19 19
4 0 0 0 0 0 0 0 0 0 0 0 0 
  1. public int dp(int[] wight, int[] value, int bag){
  2.         int[][] dp = new int[wight.length+1][bag+1];
  3.         for (int i = wight.length-1; i >= 0; i--) {
  4.             for (int j = 0; j <= bag; j++) {
  5.                 int v1 = dp[i+1][j];
  6.                 int v2 = j - wight[i] >= 0 ? (value[i] + dp[i+1][j-wight[i]]) : 0;
  7.                 dp[i][j] = Math.max(v1,v2);
  8.             }
  10.         }
  11.         return dp[0][bag];
  12. }

最长公共子序列

  1. 暴力递归

    1. // 以下为暴力递归部分代码
    2.  // text1[0....i] 和 text2[0....j]的最长公共子序列
    3.  private int run(String text1, String text2,int i, int j){
    4.      // 如果两个字符串都只有1位，相等代表有最长为1的公共子序列
    5.      if (i == 0 && j == 0){
    6.          return text1.charAt(0) == text2.charAt(0) ? 1 : 0;
    7.      }else if (i == 0){
    8.          // 如果text1的长度为1，那么如果text2当前j位置与其相等，则代表有1位，否则，当前j位可以舍弃，用j-1位再试
    9.          return text1.charAt(0) == text2.charAt(j) ? 1 : run(text1,text2,i,j-1);
    10.      }else if (j == 0){
    11.          // 与上面的情况相似
    12.          return text1.charAt(i) == text2.charAt(0) ? 1 : run(text1,text2,i-1,j);
    13.      }else {
    14.          // 如果text1和text2的长度都大于1，则有三种情况
    15.          // 如果公共子序列  可能以text1的i位置为结尾，一定不以text2的j位置为尾
    16.          int v1 = run(text1,text2,i,j-1);
    17.          // 如果公共子序列  可能以text2的j位置为结尾，一定不以text1的i位置为尾
    18.          int v2 = run(text1,text2,i-1,j);
    19.          // 如果公共子序列  一定以text1的i位置为结尾，一定以text2的j位置为尾
    20.          int v3 = text1.charAt(i) == text2.charAt(j) ? 1+run(text1,text2,i-1,j-1) : 0;
    21.          return Math.max(v1,Math.max(v2,v3));
    22.      }
    23.  }

  2. dp改造

  1. public int longestCommonSubsequence(String text1, String text2) {
  2.         if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) return 0;
  3.         int[][] dp = new int[text1.length()][text2.length()];
  4.         dp[0][0] = text1.charAt(0) == text2.charAt(0) ? 1 : 0;
  5.         // 注意j == 0时，dp[0][0]已经有值了  从1开始，下同
  6.         for (int j = 1; j < text2.length(); j++) {
  7.             dp[0][j] = text1.charAt(0) == text2.charAt(j) ? 1 : dp[0][j-1];
  8.         }
  9.         for (int i = 1; i < text1.length(); i++) {
  10.             dp[i][0] = text1.charAt(i) == text2.charAt(0) ? 1 : dp[i-1][0];
  11.         }
  12.         for (int i = 1; i < text1.length(); i++) {
  13.             for (int j = 1; j < text2.length(); j++) {
  14.                 int v1 = dp[i][j-1];
  15.                 int v2 = dp[i-1][j];
  16.                 int v3 = text1.charAt(i) == text2.charAt(j) ? 1+dp[i-1][j-1] : 0;
  17.                 dp[i][j] = Math.max(Math.max(v1,v2),v3);
  18.             }
  19.         }
  20.         return dp[text1.length()-1][text2.length()-1];
  21.     }

最长回文子序列

  1. 暴力递归 ```java public int longestPalindromeSubseq(String s) {
    1.  return run(s.toCharArray(),0,s.length()-1);
    }
  1. // str在[l...r]范围内的最长回文子序列长度
  2. private int run(char[] str,int l,int r){
  3.     if (l == r){
  4.         return 1;
  5.     }
  6.     if (l == r-1){
  7.         return str[l] == str[r] ? 2 : 1;
  8.     }
  9.     // 一共四种情况
  10.     // 一定不以l人作为左右两端
  11.     int v1 = run(str,l+1,r-1);
  12.     // 一定不以l做左端点，但可能以r为右端点
  13.     int v2 = run(str,l+1,r);
  14.     // 一定不以r做右端点，但可能以l为左端点
  15.     int v3 = run(str,l,r-1);
  16.     // 一定以lr为端点，判断相等序列长度+2并判断不以lr为端点情况，否则直接0
  17.     int v4 = str[l] == str[r] ? 2 + v1 : 0;
  18.     return Math.max(Math.max(v1,v2),Math.max(v3,v4));
  19. }
  2. 2. dp改造
  3. ```java
  4. public int longestPalindromeSubseq(String s) {
  5.         int[][] dp = new int[s.length()][s.length()];
  6.         for (int l = 0; l < dp.length; l++) {
  7.             for (int r = 0; r < dp.length; r++) {
  8.                 if (l == r){
  9.                     dp[l][r] = 1;
  10.                 }
  11.                 if (l == r-1){
  12.                     dp[l][r] = s.charAt(l) == s.charAt(r) ? 2 : 1;
  13.                 }
  14.             }
  15.         }
  16.         for (int l = s.length()-3; l >=0; l--) {
  17.             for (int r = 2+l; r <s.length(); r++) {
  18.                 // 一共四种情况
  19.                 // 一定不以l人作为左右两端
  20.                 int v1 = dp[l+1][r-1];
  21.                 // 一定不以l做左端点，但可能以r为右端点
  22.                 int v2 = dp[l+1][r];
  23.                 // 一定不以r做右端点，但可能以l为左端点
  24.                 int v3 = dp[l][r-1];
  25.                 // 一定以lr为端点，判断相等序列长度+2并判断不以lr为端点情况，否则直接0
  26.                 int v4 = s.charAt(l) == s.charAt(r) ? 2 + v1 : 0;
  27.                 dp[l][r] = Math.max(Math.max(v1,v2),Math.max(v3,v4));
  28.             }
  29.         }
  31.         return dp[0][s.length()-1];
  32.     }