🏷️ 导图

IMG_0546.JPG

(Dynamic Programming) DP

引入

  2. Q:1+1+1+1+1 = ?
  4. A:5
  6. Q:Then！ +1？
  8. A:6
  10. Q:Why?
  12. A:只要在5的基础上加1就行了,不用重新计算以前的

动态规划的核心：是记住已经解决过的子问题的解.把复杂的问题简单化，逐步分解问题。

  • 找出子结构
  • 处理边界值
  • 状态转移

两种形式

  1. 自顶向下的备忘录
  2. 自底向上

习题训练

走台阶

有N级台阶，一个人每次上一级或两级，问有多少种走完N级台阶的方法

假如有10个台阶 那么差最后一步就到达的时候可能出现的情况是第9-10 或者8-10

得出公式f(10) = f(9) + f(8).同理可得f(9) = f(8)+f(7)…f(3)=f(2)+f(1)

  1. public class Main {
  2.   public static int f(int n) {
  3.     if (n == 1)
  4.       return 1;
  5.     if (n == 2)
  6.       return 2;
  7.     return f(n - 1) + f(n - 2);
  8.   }
  10.   public static void main(String[] args) {
  11.     System.out.println(f(10));
  12.   }
  13. }

程序分析图解

动态规划 - 图2

可以看出大量重复计算。那么我们可以将计算出的结果存到一个映射结构中如果下次需要我们直接取出来

方案一:备忘录写法

  1. public class Main {
  2.   public static HashMap<Integer, Integer> map = new HashMap<>();
  4.   public static int f(int n) {
  5.     if (n == 1)
  6.       return 1;
  7.     if (n == 2)
  8.       return 2;
  10.     if (map.containsKey(n)) //看一下map中有没有这个key 如果有直接返回
  11.       return map.get(n);
  13.     int value = f(n - 1) + f(n - 2);
  14.     map.put(n, value);
  15.     return value;
  16.   }
  18.   public static void main(String[] args) {
  19.     System.out.println(f(10));
  20.   }
  21. }

复杂度从O(2²)到O(n)

方案二:递推方式

f(3) = f(2)+f(1),f(4)=f(3)+f(2) …

那么只要遍历3-10用一个for循环，设置一个临时变量放到循环体内保存前两个值的和。

  1. public class Main {
  3.   public static int f(int n) {
  4.     if (n == 1)
  5.       return 1;
  6.     if (n == 2)
  7.       return 2;
  9.     int a = 1; //上上次
  10.     int b = 2; //上一次
  11.     int temp = 0;
  12.     for (int i = 3; i <= n; i++) {
  13.       temp = a + b;
  14.       a = b;
  15.       b = temp;
  16.     }
  17.     return temp;
  19.   }
  21.   public static void main(String[] args) {
  22.     System.out.println(f(10));
  23.   }
  24. }

钢条切割

假定我们知道sering公司出售一段长度为I英寸的钢条的价格为pi(i=1,2,3….)钢条长度为整英寸如图给出价格表的描述（任意长度的钢条价格都有）。

先给我们一段长度为n的钢条，问怎么切割，获得的收益最大rn?

动态规划 - 图3

方法一：递归

  1. public static int f1(int[] p, int n) {
  2.   if (n == 0)
  3.     return 0;
  4.   int temp = 0;
  5.   for (int i = 1; i <= n; i++) {
  6.     temp = Math.max(temp, p[i] + f1(p, n - i));
  7.   }
  9.   return temp;
  10. }

数塔问题

将一些数字排成数塔形状，现在从第一层走到第二层，每次只能走向下一层连接的两个数字中的一个，问所有路径上数字和最大是多少？

动态规划 - 图4

暴力算法

计算每一条路径的长度从中找出最短路径 如果层数为k那么路径长度将接近2的k次方

DP

每步求解问题是后面阶段求解问题的子步骤每步决策依赖于以前步骤决策结果.

首先手推一下怎么走数字和最大。首先在阶段1中的第一个数字4它有两个走法要么左下要么右下，选择长的所以是9，接着第二个数字10它选取最大的数为5， 依次类推。那么到了第二阶段我们就不用计算最后一层的数和了 因为第一阶段我们已经知道了谁最大了。所以

令dp[i][j] 表示从第i行第j个数字触发的到达最底层的所有路径中能得到的最大和。

dp[1][1]就是dp[2][1] 与dp[2][2] 中的谁大 然后加上本身5

dp[1][1] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]

归纳总结：要求出dp[i][j] 一定求出他的两个子问题也就是走左边还是右边并进行一个决策（数值大的一方）而往后的比如其他层数据不用管，因此写出式子

dp[i][j] = max(dp[i+1][j] , dp[i+1][j+1]) + f[i][j]

处理边界值：数塔的最后一层dp值总等于元素本身， dp[n][j] == f[n][j]

动态规划 - 图5

  1. public class Main {
  2.     static int maxN = 100;
  4.     public static void main(String[] args){
  5.         Scanner input = new Scanner(System.in);
  6.         int n = input.nextInt(); //层数
  8.         int f[][] = new int[maxN][maxN];
  9.         int dp[][] = new int[maxN][maxN];
  11.         //输入数据
  12.         for(int i=1; i<=n; i++){
  13.             for(int j=1; j<=i; j++){
  14.                 f[i][j] = input.nextInt();
  15.             }
  16.         }
  18.         //边界值
  19.         for(int j=1; j<=n; j++){
  20.             dp[n][j] = f[n][j];
  21.         }
  23.         for(int i=n-1; i>=1; i--){
  24.             for(int j=1; j<=i; j++){
  25.                 /*状态转移方程*/
  26.                 dp[i][j] = Math.max(dp[i+1][j],dp[i+1][j+1]) +f[i][j];
  27.             }
  28.         }
  31.         System.out.println(dp[1][1]);
  34.     }
  35. }
  1. 5
  2. 5
  3. 8 3
  4. 12 7 16 
  5. 4 10 11 6
  6. 9 5 3 9 4
  7. >>> 44

分治与动态规划

都是将问题分解为子问题，然后合并子问题的解

分治法分解出的子问题是不重叠的，所以它的子问题不拥有重叠子问题。

动态规划处理的问题就是重叠子问题。主要解决最优化的问题

贪心与动态规划

共同点：拥有最优子结构

贪心算法采用的计算方式自顶向下不等待子问题求解完毕后再选择使用那个，而是直接选择一个子问题求解 没有选择的子问题就不理会了，例如数塔例子 如果贪心来求解的话是5-8-16-11-8并不一定是最优解。

动态规划总是会考虑所有子问题，并选择继承得到最优结果的那个。

所以怎么来说呢? 贪心算法只要选择了就不会后悔，那在生活中贪心比作莽夫，动态规划比作目光长远的人了吧

总结

求解过程是多阶段决策过程，每步处理一个子问题，可用于求解组合优化问题

条件：问题满足优化原则或最优子结构性质。一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列

然后动态规划的题目一般非常灵活，要根据场景来进行求解。路漫漫其修远兮，刷题去了。未完待续