动态规划问题关键特征

  • 最优子结构

    原问题的最优解涉及多个子问题 在确定最优解使用哪些子问题时，需要考虑多种选择

  • 重叠子问题

    费波纳数列image.png

    ```java package com.algorithm.demo.dongtaiguihua;

/**

  • @Author leijs

  • @date 2022/4/15 */ public class Fibnacci { public static void main(String[] args) {

    1.  long start = System.currentTimeMillis();
    2.  System.out.println(fibnacci(40));
    3.  long end = System.currentTimeMillis();
    4.  System.out.println(end - start);
    6.  long start1 = System.currentTimeMillis();
    7.  System.out.println(fibnacci2(40));
    8.  long end1 = System.currentTimeMillis();
    9.  System.out.println(end1 - start1);

    }

    public static int fibnacci2(int n) {

    1.  int[] res = new int[n + 1];
    2.  res[0] = 0;
    3.  res[1] = 1;
    4.  res[2] = 1;
    5.  if (n > 2) {
    6.      for (int i = 3; i <= n; i++) {
    7.          res[i] = res[i - 1] + res[i - 2];
    8.      }
    9.  }
    10.  return res[n];

    }

    // 递归实现 public static int fibnacci(int n) {

    1.  if (n == 1 || n == 2) {
    2.      return 1;
    3.  }
    4.  return fibnacci(n - 1) + fibnacci(n - 2);

    } }

  1. <a name="bUEBf"></a>
  2. ## 钢条切割问题
  3. ![1650033120(1).png](https://cdn.nlark.com/yuque/0/2022/png/999234/1650033132488-722b1bbd-7ac1-407b-9a73-3af68a5b231e.png#clientId=ua10111ab-2091-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=292&id=u3d288f19&margin=%5Bobject%20Object%5D&name=1650033120%281%29.png&originHeight=328&originWidth=788&originalType=binary&ratio=1&rotation=0&showTitle=false&size=72089&status=done&style=none&taskId=uf51c7921-d711-47b6-b3e3-2a75b5924c9&title=&width=700.4444444444445)<br />![1650033269(1).png](https://cdn.nlark.com/yuque/0/2022/png/999234/1650033277135-b9526cd0-a068-45eb-b559-577ba51bb2e7.png#clientId=ua10111ab-2091-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=228&id=u396e2847&margin=%5Bobject%20Object%5D&name=1650033269%281%29.png&originHeight=256&originWidth=728&originalType=binary&ratio=1&rotation=0&showTitle=false&size=67795&status=done&style=none&taskId=ubb8affc5-14f8-4efe-8841-a5c9163e488&title=&width=647.1111111111111)<br />![1650033437(1).png](https://cdn.nlark.com/yuque/0/2022/png/999234/1650033442519-219aed0c-f4ff-417e-a526-8fa561e5588b.png#clientId=ua10111ab-2091-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=291&id=u604f5350&margin=%5Bobject%20Object%5D&name=1650033437%281%29.png&originHeight=327&originWidth=764&originalType=binary&ratio=1&rotation=0&showTitle=false&size=66912&status=done&style=none&taskId=ub331ba8e-cc54-443f-91be-67c3e16690d&title=&width=679.1111111111111)<br />![1650033746(1).png](https://cdn.nlark.com/yuque/0/2022/png/999234/1650033754192-25dbdb11-e1b6-4d44-b10e-f0038a716540.png#clientId=ua10111ab-2091-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=383&id=uc8baa320&margin=%5Bobject%20Object%5D&name=1650033746%281%29.png&originHeight=431&originWidth=837&originalType=binary&ratio=1&rotation=0&showTitle=false&size=103462&status=done&style=none&taskId=u59f0eadb-1af5-4598-8cee-9d66bbd0705&title=&width=744)![image.png](https://cdn.nlark.com/yuque/0/2022/png/999234/1650034045603-44246e80-12d2-465d-be93-afcf18b01107.png#clientId=ua10111ab-2091-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=317&id=ua59228f2&margin=%5Bobject%20Object%5D&name=image.png&originHeight=357&originWidth=842&originalType=binary&ratio=1&rotation=0&showTitle=false&size=136769&status=done&style=none&taskId=u747676f4-8cea-4cba-ac72-1eb0ea4c6a6&title=&width=748.4444444444445)
  4. > 小问题的最优解可以转化为大问题的最优解
  6. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/999234/1650034258544-c51e8845-3670-4c1d-87f2-8e6d74af6522.png#clientId=ua10111ab-2091-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=334&id=u7d0eb193&margin=%5Bobject%20Object%5D&name=image.png&originHeight=376&originWidth=809&originalType=binary&ratio=1&rotation=0&showTitle=false&size=105098&status=done&style=none&taskId=u286ff3ae-6400-4930-8707-cffffb36806&title=&width=719.1111111111111)
  7. ```java
  8. package com.algorithm.demo.dongtaiguihua;
  10. import com.alibaba.fastjson.JSONObject;
  11. import com.google.common.collect.Lists;
  13. import java.util.List;
  15. /**
  16.  * @Author leijs
  17.  * @date 2022/4/15
  18.  */
  19. public class CutRod {
  20.     public static int[] price = new int[]{0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
  22.     public static void main(String[] args) {
  23.         long start = System.nanoTime();
  24.         System.out.println(cutRodRecurision(price, 9));
  25.         long end = System.nanoTime();
  26.         System.out.println(end - start);
  28.         long start1 = System.nanoTime();
  29.         System.out.println(cutRodRecurision2(price, 9));
  30.         long end1 = System.nanoTime();
  31.         System.out.println(end1 - start1);
  33.         long start2 = System.nanoTime();
  34.         System.out.println(cutRodDp(price, 9));
  35.         long end2 = System.nanoTime();
  36.         System.out.println(end2 - start2);
  38.         long start3 = System.nanoTime();
  39.         System.out.println(cutRodDpExtend(price, 9)[9]);
  40.         long end3 = System.nanoTime();
  41.         System.out.println(end3 - start3);
  42.     }
  44.     public static int cutRodRecurision2(int[] price, int n) {
  45.         // 左边不切割，右边切割的场景
  46.         if (0 == n) {
  47.             // 长度是0
  48.             return 0;
  49.         }
  50.         int res = price[n];
  51.         for (int i = 1; i <= n; i++) {
  52.             res = Math.max(res, price[i] + cutRodRecurision(price, n - i));
  53.         }
  54.         return res;
  55.     }
  57.     public static int cutRodRecurision(int[] price, int n) {
  58.         if (0 == n) {
  59.             // 长度是0
  60.             return 0;
  61.         }
  62.         int res = price[n];
  63.         for (int i = 1; i < n; i++) {
  64.             res = Math.max(res, cutRodRecurision(price, i) + cutRodRecurision(price, n - i));
  65.         }
  66.         return res;
  67.     }
  69.     public static int cutRodDp(int[] price, int n) {
  70.         int[] r = new int[n + 1];
  71.         r[0] = 0;
  72.         for (int i = 1; i <= n; i++) {
  73.             int res = 0;
  74.             for (int j = 1; j < i + 1; j++) {
  75.                 res = Math.max(res, price[j] + r[i - j]);
  76.             }
  77.             r[i] = res;
  78.         }
  79.         return r[n];
  80.     }
  82.     public static int[] cutRodDpExtend(int[] price, int n) {
  83.         int[] r = new int[n + 1];
  84.         // 左边这一段的值
  85.         int[] s = new int[n + 1];
  86.         r[0] = 0;
  87.         s[0] = 0;
  88.         for (int i = 1; i <= n; i++) {
  89.             // res价格的最优值
  90.             int res_r = 0;
  91.             // 价格最大值对应方案左边不切割部分的长度
  92.             int res_s = 0;
  93.             for (int j = 1; j < i + 1; j++) {
  94.                 if (price[j] + r[i - j] > res_r) {
  95.                     res_r = price[j] + r[i - j];
  96.                     res_s = j;
  97.                 }
  98.             }
  99.             r[i] = res_r;
  100.             s[i] = res_s;
  101.         }
  102.         System.out.println("res_s is :" + JSONObject.toJSONString(s));
  103.         List<Integer> ans = Lists.newArrayList();
  104.         while (n > 0) {
  105.             ans.add(s[n]);
  106.             n -= s[n];
  107.         }
  108.         System.out.println("ans is :" + JSONObject.toJSONString(ans));
  109.         System.out.println("r is :" + JSONObject.toJSONString(r));
  110.         return r;
  111.     }
  112. }

最长公共子序列

1650038889(1).png
1650039465(1).png
1650039541(1).png
1650039614(1).png

  1. package com.algorithm.demo.dongtaiguihua;
  3. /**
  4.  * @Author leijs
  5.  * @date 2022/4/16
  6.  */
  7. public class LcsLength {
  8.     public static void main(String[] args) {
  9.         System.out.println(lcsLength("ABCBDAB".toCharArray(), "BDCABA".toCharArray()));
  10.         System.out.println(lcs("ABCBDAB".toCharArray(), "BDCABA".toCharArray()));
  11.     }
  13.     public static int lcs(char[] a, char[] b) {
  14.         int m = a.length;
  15.         int n = b.length;
  16.         int[][] arr = new int[m + 1][n + 1];
  17.         int[][] c = new int[m + 1][n + 1]; // 1 左上方 2 上方 3 左方
  18.         for (int i = 1; i < m + 1; i++) {
  19.             for (int j = 1; j < n + 1; j++) {
  20.                 // 这两个位置字符匹配时，来自左上角 +1
  21.                 if (a[i - 1] == b[j - 1]) {
  22.                     arr[i][j] = arr[i - 1][j - 1] + 1;
  23.                     c[i][j] = 1;
  24.                 } else if (arr[i - 1][j] > arr[i][j - 1]) {
  25.                     arr[i][j] = arr[i - 1][j];
  26.                     c[i][j] = 2;
  27.                 } else {
  28.                     arr[i][j] = arr[i][j - 1];
  29.                     c[i][j] = 3;
  30.                 }
  31.             }
  32.         }
  33.         // trace back
  34.         StringBuilder sb = new StringBuilder();
  35.         int i = m;
  36.         int j = n;
  37.         while (i > 0 && j > 0) {
  38.             if (c[i][j] == 1) {
  39.                 sb.append(a[i - 1]);
  40.                 i -= 1;
  41.                 j -= 1;
  42.             } else if (c[i][j] == 2) {
  43.                 i -= 1;
  44.             } else {
  45.                 j -= 1;
  46.             }
  47.         }
  48.         System.out.println("res:" + sb);
  49.         return arr[m][n];
  50.     }
  52.     public static int lcsLength(char[] a, char[] b) {
  53.         int m = a.length;
  54.         int n = b.length;
  55.         int[][] arr = new int[m + 1][n + 1];
  56.         for (int i = 1; i < m + 1; i++) {
  57.             for (int j = 1; j < n + 1; j++) {
  58.                 // 这两个位置字符匹配时，来自左上角
  59.                 if (a[i - 1] == b[j - 1]) {
  60.                     arr[i][j] = arr[i - 1][j - 1] + 1;
  61.                 } else {
  62.                     arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
  63.                 }
  64.             }
  65.         }
  66.         return arr[m][n];
  67.     }
  68. }