推导动态规划问题的公式

柔情只为你懂 2022-09-16 08:40 279阅读 0赞

> 学如逆水行舟，不进则退。当我对算法题的概念还停留在1000题的时候，今天打开力扣一看，已经更新到1900道题了。真的是，没有进步就是在退步。 意识到了算法的重要性，也想通过算法来给自己提升一点自信，又或者说给自己增加一点底气！

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5rC055qE57K-56We_size_20_color_FFFFFF_t_70_g_se_x_16][]

我始终认为，算法题这个东西，它是一个闻道有先后的问题，并不是和智商挂钩的问题。 但是算法也是始终压在我身上的一座大山。翻不过去，我永远都是弟弟。

最近在摸索一些解题思路，和解题技巧。我会用脑图，加文字，加图片的形式来记录自己的学习和领悟的过程。

# 正式开始动态规划 #

## 先说说为什么是从动态规划开始 ##

打开力扣刷题网站，选上动态规划标签。光是动态规划问题，就有350道。上边说了，目前力扣上一共也就又1900道。

所以如果把动态规划问题刷明白了，一下子就会了好多道题。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5rC055qE57K-56We_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

每页50道，一共7页，一共350题，都是动态规划的。足矣展示动态规划的重要性了。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5rC055qE57K-56We_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

##  ##

## 动态规划问题语义解析 ##

从名字中，我们可以得到两个问题。从 “**动态**” 我们可以推出 “**状态**”，我也喜欢称作**变量**。“规划”二字，我们要想到的是“**选择**”，所谓规划也就是选择最好的结果，也叫做“**择优**”。

所以动态规划问题就是在不同的状态中选择出最佳的状态，最终得到问题的解。

## 动态规划问题思路梳理 ##

先总结一下动态问题的**形态特征**。也就是先能辨别到底什么是动态规划问题。或者说，什么时候我去用动态规划来解决问题。

### 动态规划问题的**形态特征** ###

*  动态规划最最最常见的就是求最值问题。最长，最短，最多，最少。

（这是基于我刷题经历来总结，随着题量的增加，会回来补充）

### 基于现象看本质 - 动态规划的本质是暴力列举所有可能性（穷举） ###

那么根据我们上边总出来的动态规划问题的特征，来想一个本质上的问题。

我先说一个我的认知：计算机是一个非常笨的机器，它没有思维模式的，也不会去主动想问题。那么基于这一点呢，关于最什么什么的问题，计算机只能通过暴露的方式，找到所有的可能性，然后从中对比出最优解。不管是最长还是最短，还是多最少。本质上都一样。

基于这个本质问题，我们就要养成一个习惯，在看到类似的求最值问题时，首先想的是如何穷举所有的可能性。如果去coding出来所有的可能性。然后再是利用一些技巧去优化我们的算法。

### 动态规划问题的结构 ###

我感觉动态固化问题有分治思想在的，就是**把大问题化成小问题**，**最终的求解是在小问题得到解决的基础上**的。所以动态规划问题，具备子结构的问题。动态规划要解决的最大的问题，是在暴力穷举过程中，解决重复的**子结构**问题（子结构第一次出现，在下边的栗子中，会说明什么是子结构）。 所以，它一般情况下，都需要用到一个辅助空间（也可以说是备忘录），来记录这些子问题的解。用专业的术语描述，就是dp数组（dp数组第一次出现，在下边的栗子中，会说明什么是子结构））。

### 小总结 ###

到这里，我们应该明白，动态规划问题，实际上就是用一个**备忘录**，来记录所有可能性的结果。然后**暴力穷举**所有的结果。最后是在备忘录中找到最好的结果。

## 动态规划问题细节，抽丝剥茧来解决 ##

结合上边讲的，我们想要解决一个动态规划问题的时候，要思考两件事：第一件是**如何暴力穷举**；第二件是如何设计备忘录，也就是 dp数组。

看似简单就四个字，暴力穷举。但是难就难在了暴力穷举。上边铺垫那么多文字，就是想让大家在心里默默接受暴力穷举这四个字。接下来我们再看看穷举的细节，如何穷举。剩下的就是多看一些题，来找找感觉。

###  如何做到动态规划的穷举？ ###

这是最核心，也是最难的问题。能够解决这个问题，实际上已经完成了百分之八十。穷举，不是你脑补出来所有的可能性，然后从代码一行一行敲出来。那得把我们累死。而是找到状态转移方程。用公式，来描述所有可能性，然后让计算机去完成计算。所以能够否解决问题，在于我们能否写出状态转移方程。

### 关于如何写出状态转移方程 ###

1. 找到base case。也就是找到最基础的案例。这是一个蛮关键的点，因为递归的时候，它是我们程序的一个退出点。

2. 根据上边对动态规划的语义分析，**我们要找变化的状态是什么，也就是说都有什么是变量**。

3. 然后是选择，**如何去选择最有的状态**。前提肯定是列出所有的情况才能找到最有的状态。

### 那如何才算列出来所有的情况呢？ ###

答案是用公式，或者说固定结构。

再回头看一下我对“动态规划”的语义分析。提到了状态，和变量的问题。来想一下我下边的公式是否合理？ 我下边的公式是否能够列出来所有的情况？ 如有没有问题话，请好好记住这个穷举的公式。

for （变量一  in  变量一的所有取值情况 ）{
    
              for （变量二  in  变量二的所有取值情况） {
    
                      // TODO something
    
                      择优
    
              }
    
       }

# 来一个栗子，来验证公式 #

## 经典的动态规划问题- 01 背包问题 ##

来看问题描述：

> 给你一个可装载重量为`W`的背包和`N`个物品，每个物品有重量和价值两个属性。其中第`i`个物品的重量为`wt[i]`，价值为`val[i]`，现在让你用这个背包装物品，最多能装的价值是多少？
> 
> 举个简单的例子，输入如下：
> 
>     N = 3, W = 4
>     wt = [2, 1, 3]
>     val = [4, 2, 3]
> 
> 算法返回 6，选择前两件物品装进背包，总重量 3 小于`W`，可以获得最大价值 6。

## 动态规划要解决第一个问题：穷举过程的解题思路 ##

我们第一步，要找变量是什么，这道题的最关键的点就是找对变量，选对变量。这需要我们去刷非常多的题，来找题感。

好好的读几遍题，我找到的变量有：

1.  第i个物品的价值 vul\[i\]
2.  第i个物品的重量 wt\[i\]
3.  背包可装载重量W

ok，从三行题上，我们能看出来的变量只有这么多。但是它们都要用做循环体吗？答案是否定的，仔细想一下，上边列出来的第一条变量，以及第二条变量是不是可以合并成第i个我物品？因为前两个变量都属于一个物品的属性。

所以更新后的变量只有两条：

1.  第i个物品
2.  背包可容量W

我们已经找到了变量，接着可以套我们的公式了

// 变量一 为第i个物品
    for (int i = 1; i <= N; i++) {
         // 变量二 为背包的容量
         for (int w = 1; w <= W; w++) {
             // todo 择优过程 ...
         }
    }

问题到了这里，我们已经列出来了所有的可能性，也就是完成了穷举的过程了。解析来，继续探讨第二个问题，**择优**的过程。

## 动态规划要解决第一个问题：择优过程的解题思路 ##

既然是择优，那么就要明白另外一件事，可以做的选择有哪些？也就是在穷举的过程中，可以做出哪些选择?

对于这道题，比较明显，很容易想到的是：第i个物品是否要放到背包中。这道题之所以叫做 01 背包问题，有一个原因就是，选择实际上只有两种可能，要么选，要么不选，选就是把物品放入背包，不选就是不把这个物品放入背包。

究竟要不要选择，不是随便说的，是对比出来的。那么新的问题来了，谁和谁对比呢？对于这道题而言，实际上，是选当前物品放入背包的结果，和不选当前物品放入背包的结果。

这里需要引入一个概念了，就是上文提到的dp数组，也叫做备忘录。这个dp数组是和上边的变量对照起来的。两个变量就是二位数组，每一维度代表的是一个变量。来直接看代码：

// 变量一 为第i个物品
    for (int i = 1; i <= N; i++) {
         // 变量二 为背包的容量
         for (int w = 1; w <= W; w++) {
             // todo 择优过程 ...
            dp[i][w] = Math.max(
                dp[i-1][w],
                dp[i-1][w - wt[i-1]] + val[i-1]
            )
         }
    }

上边的代码还是有遗漏的地方。因为没有考虑到背包放不下当前物品的情况。这就是程序必不可少的扣边界的问题。其实很简单，只要能想到这个问题，很容易就能解决。看代码：

// 变量一 为第i个物品
    for (int i = 1; i <= N; i++) {
         // 变量二 为背包的容量
         for (int w = 1; w <= W; w++) {
             // todo 择优过程 ...
             if (w - wt[i-1] < 0) {
                    // 当前背包容量装不下，只能选择不装入背包
                    dp[i][w] = dp[i - 1][w];
                } else {
                    // 装入或者不装入背包，择优
                    dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1], 
                                   dp[i - 1][w]);
              }
         }
    }

重点来看注释 择优过程下边的三行代码。这就是择优过程，前边已经提过了，要选择的就是：是选当前物品放入背包的结果，和不选当前物品放入背包的结果。选出来以后，把最优解给了 dp\[i\]\[w\]。 到了这里应该能够明白，为什么dp数组，又叫做备忘录，实际上呢，它记录了历史的结果。至于为什么要记，是因为历史的结果会影响到接下来的操作，应为我们不能保证历史操作就是最优解。所以说全局最优解才是最优解，局部最优解并不一定是最终的最优解！

## 第三步，动态规划的收尾工作 ##

前边两步，已经解决了动态规划最核心的问题。代码也基本上完成了。再补充一些收尾工作。比方说初始化用到的 dp数组，返回最终结果。

接着把代码补全：

public class ZeroOnePack {
        // N表示物体的个数，V表示背包的载重
        int N = 3, W = 4;
        //二维数组，备忘录
        private int[][] dp;
     
        /**
         * 使用非递归方式，求解F[0 .. N][0 .. V]，即for循环从下至上求解
         */
        public nt[][] ZeroOnePackNonRecursive() {
            //对二维数组进行初始化
            for(int j = 0; j <= W; j++) {
                dp[0][j] = 0;
            }
     
         
            // 变量一 为第i个物品
            for (int i = 1; i <= N; i++) {
                 // 变量二 为背包的容量
                 for (int w = 1; w <= W; w++) {
                     // todo 择优过程 ...
                     if (w - wt[i-1] < 0) {
                     // 当前背包容量装不下，只能选择不装入背包
                     dp[i][w] = dp[i - 1][w];
                 } else {
                    // 装入或者不装入背包，择优
                    dp[i][w] = Math.max(dp[i - 1][w - wt[i-1]] + val[i-1], 
                                   dp[i - 1][w]);
                      }
                 }
            }
     
            //打印所有结果，来验证一下。我们要求的最终结果是dp[N][W]
            for(int i = 0; i <= N; i++) {
                for(int j = 0; j <= V; j++) {
                    System.out.print(F[i][j] + " ");
                }
                System.out.println();
            }
            return dp[N][W];
        }
    }

##  ##

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5rC055qE57K-56We_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/43486c37eb044dd6bed796999f2211ea.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5rC055qE57K-56We_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/e2f412a110f548c5ad40327231f04baf.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5rC055qE57K-56We_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/a4ccb4fca2314ee98ce268f33072d215.png