【数据结构与算法】【算法思想】动态规划

矫情吗；* 2022-12-01 14:19 267阅读 0赞

贪心算法  
回溯算法  
分治算法  
**动态规划**

贪心：一条路走到黑，就一次机会，只能哪边看着顺眼走哪边  
回溯：一条路走到黑，无数次重来的机会，还怕我走不出来 (Snapshot View)  
动态规划：拥有上帝视角，手握无数平行宇宙的历史存档， 同时发展出无数个未来 (Versioned Archive View)

初识动态规划、动态规划理论、动态规划实战

### 初识动态规划 ###

动态规划比较适合用来求解最优问题，比如求最大值，最小值等。可以非常显著地降低时间复杂度，提高的执行效率。

#### 0-1背包问题 ####

##### 使用回溯算法： #####

使用回溯法复杂度比较高，是指数级别的，规律不好找。递归树中的每个节点表是一种状态，我们用（I,cw）来表示。其中，i表示将要决策第几个物品是否要装入背包，cw表示当前背包中物品的总重量。如（2,2）表示我们将要决策第2个物品是否要装入背包，在决策前，背包中的物品总重量是2。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

从递归树中，可发现有些子问题的求解是重复的，如图中f(2,2)和f(3,4)都被重复计算了两次。我们可借助“备忘录”的解决方式，记录已经计算好的f(I,cw)，当再次计算到重复的f(I,cw)的时候，可以直接从**备忘录**中取出来用，就不用在递归计算了，这样就可以避免冗余计算。

private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
    private int[] weight = { 2，2，4，6，3};  // 物品重量
    private int n = 5; // 物品个数
    private int w = 9; // 背包承受的最大重量
    private boolean[][] mem = new boolean[5][10]; // 备忘录，默认值false
    public void f(int i, int cw) {  // 调用f(0, 0)
      if (cw == w || i == n) {  // cw==w表示装满了，i==n表示物品都考察完了
        if (cw > maxW) maxW = cw;
        return;
      }
      if (mem[i][cw]) return; // 重复状态
      mem[i][cw] = true; // 记录(i, cw)这个状态
      f(i+1, cw); // 选择不装第i个物品
      if (cw + weight[i] <= w) { 
        f(i+1,cw + weight[i]); // 选择装第i个物品
      }
    }

##### 使用动态规划算法： #####

把整个求解过程分为n个阶段，每个阶段会决策一个物品是否放置到背包中。每个物品决策（放入或者不放入背包）完之后，背包中的物品的重量会有很都情况，会达到多种不同的状态，对应到递归树中，就是很多不同的节点。  
把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过w个（w表示背包的承载重量），这就避免了每层状态个数的指数级增长。  
用一个二维数组states\[n\],\[w+1\]，来记录每层可以达到的不同状态

第0个（下标从0开始编号）物品的重量是2，要么转入背包，要么不装入背包，决策完之后，会对应背包的两种状态，背包中物品的总重量是0或者2。我们用states\[0\]\[0\]=true和states\[0\]\[2\]=true来表示这两种转态。  
第1个物品的重量也是2，基于之前的背包状态，在这个物品决策完之后，不同的状态有3个，背包中物品总重量分别是0(0+0)，2(0+2 or 2+0)，4(2+2)。我们用states\[1\]\[0\]=true，states\[1\]\[2\]=true，states\[1\]\[4\]=true来表示这三种状态。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

weight:物品重量，n:物品个数，w:背包可承载重量
    public int knapsack(int[] weight, int n, int w) { 
      boolean[][] states = new boolean[n][w+1]; // 默认值false
      states[0][0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
      if (weight[0] <= w) { 
        states[0][weight[0]] = true;
      }
      for (int i = 1; i < n; ++i) {  // 动态规划状态转移
        for (int j = 0; j <= w; ++j) { // 不把第i个物品放入背包
          if (states[i-1][j] == true) states[i][j] = states[i-1][j];
        }
        for (int j = 0; j <= w-weight[i]; ++j) { //把第i个物品放入背包
          if (states[i-1][j]==true) states[i][j+weight[i]] = true;
        }
      }
      for (int i = w; i >= 0; --i) {  // 输出结果
        if (states[n-1][i] == true) return i;
      }
      return 0;
    }

用回溯算法解决这个问题的时间复杂度O(2^n)，是指数级的。动态规划方案的时间复杂度是O(n\*w)。n表是物品个数，w表是背包可以承载的总重量。  
尽管动态规划的执行效率比较高，但是我们需要额外申请一个n乘以w+1的二维数组，对空间消耗比较多。所以动态规划是一种**空间换时间**的解决思路。  
但实际上，只需要一个大小为w+1的一维数组就可以解决这个问题。动态规划状态转移的过程，都可以基于这个一维数组来操作。

public static int knapsack2(int[] items, int n, int w) { 
      boolean[] states = new boolean[w+1]; // 默认值false
      states[0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
      if (items[0] <= w) { 
        states[items[0]] = true;
      }
      for (int i = 1; i < n; ++i) {  // 动态规划
        for (int j = w-items[i]; j >= 0; --j) { //把第i个物品放入背包
          if (states[j]==true) states[j+items[i]] = true;
        }
      }
      for (int i = w; i >= 0; --i) {  // 输出结果
        if (states[i] == true) return i;
      }
      return 0;
    }

#### 0-1背包问题升级版 ####

基础的背包问题，只涉及背包的重量和物品重量，现在引入物品价值这个一个变量。对于一组不同重量，不同价值，不可分割的物品，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少？

采用回溯算法：  
在递归树中，每个节点表示一个状态，需要3个变量（I，cw，cv）来表示一个状态。其中，i表示即将要决策第i个物品是否装入背包，cw表示当前背包中物品的总重量，cv表示总价值。  
在递归树中，有几个节点的i和cw是完全相同的，比如f(2,2,4)和f(2,2,3)。在背包中物品总重量一样的情况下，f(2,2,4)这种状态对应的物品总价值更大，可以舍弃f(2,2,3)这种状态，只需要沿着f(2,2,4),这条策略线继续往下决策就可以  
即对于（I,cw）相同的不同状态，我们只需要保留cv值最大的那个，继续递归处理，其他状态不予考虑。

private int maxV = Integer.MIN_VALUE; // 结果放到maxV中
    private int[] items = { 2，2，4，6，3};  // 物品的重量
    private int[] value = { 3，4，8，9，6}; // 物品的价值
    private int n = 5; // 物品个数
    private int w = 9; // 背包承受的最大重量
    public void f(int i, int cw, int cv) {  // 调用f(0, 0, 0)
      if (cw == w || i == n) {  // cw==w表示装满了，i==n表示物品都考察完了
        if (cv > maxV) maxV = cv;
        return;
      }
      f(i+1, cw, cv); // 选择不装第i个物品
      if (cw + weight[i] <= w) { 
        f(i+1,cw+weight[i], cv+value[i]); // 选择装第i个物品
      }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

采用动态规划算法：  
还是把整个求解过程分为n个状态，每个阶段会决策一个物品是否放到背包中。每个决策完之后，背包中的物品的总重量以及总价值，会有多种情况，也就是会达到多种不同的状态。  
用一个二维数组states\[n\]\[w+1\]，来记录每层可以达到的不同状态。不过这里数组存储的值不在是boolean类型的了，而且当前状态对应的最大总价值，我们把每一层中（I,cw）重复的状态（节点）合并，只记录了cv值最大的那个状态，然后基于这些状态来推导下一层的状态。

public static int knapsack3(int[] weight, int[] value, int n, int w) { 
      int[][] states = new int[n][w+1];
      for (int i = 0; i < n; ++i) {  // 初始化states
        for (int j = 0; j < w+1; ++j) { 
          states[i][j] = -1;
        }
      }
      states[0][0] = 0;
      if (weight[0] <= w) { 
        states[0][weight[0]] = value[0];
      }
      for (int i = 1; i < n; ++i) {  //动态规划，状态转移
        for (int j = 0; j <= w; ++j) {  // 不选择第i个物品
          if (states[i-1][j] >= 0) states[i][j] = states[i-1][j];
        }
        for (int j = 0; j <= w-weight[i]; ++j) {  // 选择第i个物品
          if (states[i-1][j] >= 0) { 
            int v = states[i-1][j] + value[i];
            if (v > states[i][j+weight[i]]) { 
              states[i][j+weight[i]] = v;
            }
          }
        }
      }
      // 找出最大值
      int maxvalue = -1;
      for (int j = 0; j <= w; ++j) { 
        if (states[n-1][j] > maxvalue) maxvalue = states[n-1][j];
      }
      return maxvalue;
    }

### 动态规划理论 ###

动态规划理论之**最优子结构，无后效性和重复子问题**

1，“一个模型三个特征”理论讲解  
什么样的问题适合用动态规划来解决？  
**（1）“一个模型”**  
它指的是动态规划适合解决的问题的模型，**“多阶段决策最优解模型”**。  
一般是用动态规划来解决最优问题，而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。  
**（2）“三个特征”：**  
他们分别是**最优子结构，无后效性和重复子问题**  
**1，最优子结构：**  
最优子结构指的是，问题的最优解包含子问题的最优解。即反之讲，可以通过子问题的最优解，推导出问题的最优解。  
若把最优子结构，对应到前面定义的动态规划问题模型上，也可以理解为后面阶段的状态可以通过前面阶段的状态推导出来。  
**2，无后效性：**  
无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步步推导出来的，第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响，无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，基本上都会满足无后效性。  
**3，重复子问题**  
不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态

**两种动态规划解题思路总结**  
解决动态规划问题，一般有两种思路，分别可叫作，状态转移表法和状态转移方程法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]  
用回溯算法来解决这个问题。如果你自己写一下代码，画一下递归树，就会发现，递归树中有重复的节点。重复的节点表示，从左上角到节点对应的位置，有多种路线，这也能说明这个问题中存在**重复子问题**。  
如果我们走到 (i, j) 这个位置，我们只能通过 (i-1, j)，(i, j-1) 这两个位置移动过来，也就是说，我们想要计算 (i, j) 位置对应的状态，只需要关心 (i-1, j)，(i, j-1) 两个位置对应的状态，并不关心棋子是通过什么样的路线到达这两个位置的。而且，我们仅仅允许往下和往右移动，不允许后退，所以，前面阶段的状态确定之后，不会被后面阶段的决策所改变，所以，这个问题符合“**无后效性**”这一特征。  
刚刚定义状态的时候，我们把从起始位置 (0, 0) 到 (i, j) 的最小路径，记作 min\_dist(i, j)。因为我们只能往右或往下移动，所以，我们只有可能从 (i, j-1) 或者 (i-1, j) 两个位置到达 (i, j)。也就是说，到达 (i, j) 的最短路径要么经过 (i, j-1)，要么经过 (i-1, j)，而且到达 (i, j) 的最短路径肯定包含到达这两个位置的最短路径之一。换句话说就是，min\_dist(i, j) 可以通过 min\_dist(i, j-1) 和 min\_dist(i-1, j) 两个状态推导出来。这就说明，这个问题符合“**最优子结构**”。

**1，状态转移表法**  
**回溯法-〉递归树-〉重复子问题-〉备忘录/动态规划**  
一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。所以，当拿到问题时，可以先用简单的回溯算法解决，然后定义状态，每个状态表示一个节点，然后对应画出递归树。  
从递归树中，很容易可以看出是否存在重复子问题，以及重复子问题是如何产生的。以此来寻找规律，看是否能用动态规划解决。  
找到重复子问题之后，有两种处理思路，\*\*第一种是直接用回溯加“备忘录”的方法，来避免重复子问题。\*\*从执行效率上来将，这和动态规划的解决思路没有差别，**第二种是使用动态规划的解决方法，状态转移表法。**  
**回溯**

private int minDist = Integer.MAX_VALUE; // 全局变量或者成员变量
    // 调用方式：minDistBacktracing(0, 0, 0, w, n);
    public void minDistBT(int i, int j, int dist, int[][] w, int n) { 
      // 到达了n-1, n-1这个位置了，这里看着有点奇怪哈，你自己举个例子看下
      if (i == n && j == n) { 
        if (dist < minDist) minDist = dist;
        return;
      }
      if (i < n) {  // 往下走，更新i=i+1, j=j
        minDistBT(i + 1, j, dist+w[i][j], w, n);
      }
      if (j < n) {  // 往右走，更新i=i, j=j+1
        minDistBT(i, j+1, dist+w[i][j], w, n);
      }
    }

**递归树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]

**重复子问题**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 7]

**备忘录/动态规划**

public int minDistDP(int[][] matrix, int n) { 
      int[][] states = new int[n][n];
      int sum = 0;
      for (int j = 0; j < n; ++j) {  // 初始化states的第一行数据
        sum += matrix[0][j];
        states[0][j] = sum;
      }
      sum = 0;
      for (int i = 0; i < n; ++i) {  // 初始化states的第一列数据
        sum += matrix[i][0];
        states[i][0] = sum;
      }
      for (int i = 1; i < n; ++i) { 
        for (int j = 1; j < n; ++j) { 
          states[i][j] = 
                matrix[i][j] + Math.min(states[i][j-1], states[i-1][j]);
        }
      }
      return states[n-1][n-1];
    }

状态转移表法  
先画出一个状态表，状态表一般都是二维的其中每个状态包含三个变量，行，列，数组值。我们根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，将这个递推填表的过程，翻译成代码，就是动态规划代码了。

**状态转移方程法：**  
状态转移方程有点类似递归的解题思路，需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。有了状态转移方程，代码实现就非常简单了，一般情况下，有两种代码实现的方法，**一种是递归加“备忘录”，另一种是迭代递推。**

private int[][] matrix = 
             { { 1，3，5，9}, { 2，1，3，4}，{ 5，2，6，7}，{ 6，8，4，3}};
    private int n = 4;
    private int[][] mem = new int[4][4];
    public int minDist(int i, int j) {  // 调用minDist(n-1, n-1);
      if (i == 0 && j == 0) return matrix[0][0];
      if (mem[i][j] > 0) return mem[i][j];
      int minLeft = Integer.MAX_VALUE;
      if (j-1 >= 0) { 
        minLeft = minDist(i, j-1);
      }
      int minUp = Integer.MAX_VALUE;
      if (i-1 >= 0) { 
        minUp = minDist(i-1, j);
      }
      
      int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);
      mem[i][j] = currMinDist;
      return currMinDist;
    }

状态转移方程是解决动态规划的关键，如果能写出状态转移方程，那动态规划问题基本上就解决一大半了，但是很多动态规划问题的状态本身就不好定义，状态转移方程也就更不好想到。

**状态转移表法解题思路大致可以概括为，回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。  
状态转移方程法的大致思路可以概括为，找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码。**

动态规划实战

**实现搜索引擎中的拼写纠错功能**

编辑距离

莱文斯坦距离（Levenshtein distance）和最长公共子串长度（Longest common substring length）。其中，莱文斯坦距离允许增加、删除、替换字符这三个编辑操作，最长公共子串长度只允许增加、删除字符这两个编辑操作。

**莱文斯坦距离（Levenshtein distance）**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][20200828202652838.png_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 9]  
**最长公共子串长度**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 10]  
![在这里插入图片描述][20200828202733134.png_pic_center]  
当用户在搜索框内，输入一个拼写错误的单词时，我们就拿这个单词跟词库中的单词一一进行比较，计算编辑距离，将编辑距离最小的单词，作为纠正之后的单词，提示给用户。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 11]

\[笔记整理来源： 王争 数据结构与算法之美\](htt ps://s1.ax1x.com/2020/08/03/aUh2TS.png)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1ba39c1533c94541a3c77b164ecfc4d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/d80a6976789b4a138a31840234a6ef0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/94251be35b45470c981ed639a59619c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/3ee49fb0e77c4a658ccc23f7bc7cc58e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/47cda46be97b4ab0b0a2b98ff1287bd2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/be16e52e2dd24d57afb99c6d6ba663a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/d36870363fb64c79a25eaabbf50a2b7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/8af14f6a443047739441664f42d8b1e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/60e84a8a63e34d9bb36c387e46fe270f.png
[20200828202652838.png_pic_center]: /images/20221123/25b2fdd677ed4aa48934d73acc1ec2e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/6713fbff54794ca7a2668a14242a0bb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221123/864085cf6abb4269afe3bdda56302e65.png
[20200828202733134.png_pic_center]: /images/20221123/8e9941b15f884340b0cf716eea601c68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221123/1bfadeae1eb2465e9f80fabf3883176c.png