2021-10-19 动态规划

小咪咪 2022-09-16 12:21 118阅读 0赞

### 文章目录 ###

*   *   *   *   *  0. 入门须知
                 *  1.能用动态规划解决的问题
                 *  2. 适合用动态规划解决的问题
                 *  3. 应用动态规划(三个子目标)
                 *  4. 高中数列题的升级版
                 *  5. 例子

##### 0. 入门须知 #####

***入门第一条：切忌望文生义，切忌用名字反推算法***  
***入门第二条：区别通项公式和递推公式，通项公式输入n，输出f(n)，而递推公式输入f(n-1),输出f(n)***

--------------------

##### 1.能用动态规划解决的问题 #####

1). **问题的答案依赖于问题的规模，也就是问题的所有答案构成了一个数列**。举个简单的例子，1个人有2条腿，2个人有4条腿，…，n个人有多少条腿？答案是 2n条腿。这里的n是问题的答案， 2n则是问题的规模，显然问题的答案是依赖于问题的规模的。答案是因变量，问题规模是自变量。因此，问题在所有规模下的答案可以构成一个数列 \[f(1),f(2),…,f(n)\]，比如刚刚“数腿”的例子就构成了间隔为2的等差数列\[0,2,4,…,2n\]。  
2). **大规模问题的答案可以由小规模问题的答案递推得到，也就是f(n)的值可以由f(i),i<n中的个别求得**。还是刚刚“数腿”的例子，显然 f(n)可以基于f(n-1)求得： f(n)=f(n-1)+2。

--------------------

##### 2. 适合用动态规划解决的问题 #####

能用动态规划解决，不代表适合用。比如刚刚的“数腿”例子，你可以写成 f(n)=2n的显式表达式形式，那么杀鸡就不必用牛刀了。但是，在许多场景，**f(n)的显式式子是不易得到的，大多数情况下甚至无法得到**，动态规划的魅力就出来了。

--------------------

##### 3. 应用动态规划(三个子目标) #####

当要应用动态规划来解决问题时，归根结底就是想办法完成以下三个关键目标。  
1). **建立状态转移方程**  
这一步是最难的，大部分人都被卡在这里。这一步没太多的规律可说，只需抓住一个思维：当做已经知道f(1)~f(n-1)的值，然后想办法利用它们求得f(n)。在“数腿”的例子中，状态转移方程即为f(n)=f(n-1)+2。  
2). **缓存并复用以往结果**  
这一步不难，但是很重要。如果没有合适地处理，很有可能就是指数和线性时间复杂度的区别。假设在“数腿”的例子中，我们不能用显式方程，只能用状态转移方程来解。如果现在f(100)未知，但是刚刚求解过一次 f(99)。如果不将其缓存起来，那么求f(100)时，我们就必须花100次加法运算重新获取。但是如果刚刚缓存过，只需复用这个子结果，那么将只需一次加法运算即可。  
3). **按顺序从小往大算**  
这里的“小”和“大”对应的是问题的规模，在这里也就是我们要从 f(0), f(1) , … 到f(n)依次顺序计算。这一点在“数腿”的例子来看，似乎显而易见，因为状态方程基本限制了你只能从小到大一步步递推出最终的结果（假设我们仍然不能用显式方程）。然而当问题复杂起来的时候，你有可能乱了套，所以必须记住这也是目标之一。

##### 4. 高中数列题的升级版 #####

看到这里，你可能会觉得怎么跟高中的数列题那么像？？其实这就是高中数列题的升级版。

高中的题一般需先推导出状态转移方程(**递推公式**)，再据此推导出显式表达式（**通项公式**）。然而，动态规划是要我们在推导出状态转移方程(**递推公式**)后，根据状态转移方程用计算机暴力求解出来。显式表达式？在动态规划中是不存在的！

就是因为要暴力计算，所以前面说的目标有两个是涉及到代码层面上：

*  缓存中间结果：也就是搞个数组之类的变量记录中间结果。
 *  按顺序从小往大算：也就是搞个for循环依次计算。

##### 5. 例子 #####

接下来用3个例子印证上面的思想。例子是从简单，困难到地狱级别的题目。

1). **斐波那契数列（简单-一维）**

斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
    它遵循这样的规律：当前值为前两个值的和。
    那么第n个值为多少？

首先，我们可以很容易得到状态转移方程：f(n)=f(n-1)+f(n-2)。

接下来我们用两种方法来做：

1.简单递归(反例)

def fib(n):
        if n < 2:
            return n
        else:
            return fib(n-1) + fib(n-2)
        
    if __name__ == '__main__':
        result = fib(100)  # 你等到天荒地老，它还没有执行完

如上所示，代码简单易懂，然而这代码却极其低效。先不说这种递归的方式造成栈空间的极大浪费，就仅仅是该算法的时间复杂度已经属于O(2^n) 了。指数级别时间复杂度的算法跟不能用没啥区别！

2.动态规划

def fib(n):
        
        results = list(range(n+1)) # 用于缓存以往结果，以便复用（目标2）
        
        for i in range(n+1):  # 按顺序从小往大算（目标3）,先算f(0)
            if i < 2:
                results[i] = i
            else:
                # 使用状态转移方程（目标1），同时复用以往结果（目标2）
                results[i] = results[i-1] + results[i-2] 
        return results[-1]
        
    if __name__ == '__main__':
        result = fib(100)  # 秒算，result为：354224848179261915075

如上代码，针对动态规划的三个子目标，都很好地实现了（参考备注）。

2). **不同路径（困难-二维）**

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
    问总共有多少条不同的路径？
    例如，下图是一个7 x 3 的网格。有多少可能的路径？
    
    提示：
    1 <= m, n <= 100
    题目数据保证答案小于等于 2 * 10^9

![在这里插入图片描述][3ee6d1933c7d4e139d4d77e4b51d8ddf.png]  
***先自己思考1min……再看答案***

解这题，如前所述，我们需要完成三个子目标:

1.建立状态转移方程。该题就难在这里，这一步搞不定基本上GG了。实际上，如图3所示，第i行第j列的格子的路径数，是等于它左边格子和上面格子的路径数之和：f(i,j)=f(i-1,j)+f(i,j-1)。  
![图3 状态转移方程推导图解][3]  
2.缓存并复用以往结果。与之前说的一维数列不同，这里的中间结果可以构成一个二维数列（如图3），所以需要用二维的数组或者列表来存储。

3.按顺序从小往大算。这次有两个维度，所以需两个循环，分别逐行和逐列让问题从小规模到大规模计算。

# m是行数，n是列数
    def count_paths(m, n):    
        
        results = [[1] * n] * m  # 将二维列表初始化为1，以便之后用于缓存（目标2）
        # 题外话：results的空间复杂度不是O(nm)，是O(n)
        
        # 第0行和第0列的格子路径数显然均取值为1，所以跳过
        for i in range(1, m):       # 外循环逐行计算（目标3）
            for j in range(1, n):   # 内循环逐列计算（目标3）    
                # 状态方程（目标1），以及中间结果复用（目标2）
                results[i][j] = results[i-1][j] + results[i][j-1]  
                
        return results[-1][-1]
    
    
    if __name__ == '__main__':
        result = count_paths(7, 3) # 结果为28

**3) 正则表达式匹配（地狱）**

提示：
    
    1 <= s.length <= 20
    1 <= p.length <= 30
    s 可能为空，且只包含从 a-z 的小写字母。
    p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
    保证每次出现字符 * 时，前面都匹配到有效的字符.
    
    提示：
    1 <= s.length <= 20
    1 <= p.length <= 30
    s 可能为空，且只包含从 a-z 的小写字母。
    p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
    保证每次出现字符 * 时，前面都匹配到有效的字符

***可以先自己思考3min……再看答案。***

1.建立状态转移方程。这里的状态转移方程有些复杂，我折腾了一段时间才总结出来的，如果看不懂就跳过不用纠结，毕竟文章的重点不在此。

*  首先我们进行如下定义:  
    f(i,j)：pattern的第0 ~ i个字符与string的第0 ~ j个字符的匹配结果。结果只取True（匹配成功），或者False（匹配失败）。  
    Pi：pattern的第i个字符。  
    Si：string的第j个字符。  
    m(i,j)：单个字符Pi和Sj的匹配结果。结果只取True（匹配成功），或者False（匹配失败）。  
    那么参考如图4，可得下面的状态转移方程。具体地说有两种情况（看不懂这里就跳过吧，篇幅有限不能大书特书）：  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbWJzaHFxYg_size_20_color_FFFFFF_t_70_g_se_x_16]

(1). 如果Pi为星号外的任意字符，用“x”表示。这种情况显而易见，f(i,j)是基于f(i-1,j-1)的结果（可能成功或者失败的）继续配对。  
(2). 如果Pi为星号“\*”。如图4右边，分三种子情况。  
**箭头1**描述了Pi-1匹配成功了0次的情况，所以继承前面匹配的结果f(i-2,j)；  
**箭头2**描述了Pi-1 成功匹配了1次的情况，所以继承这1次的结果f(i-1,j)；  
**箭头3**表示Pi-1成功匹配超过1次，所以基于左边的结果继续匹配f(i,j-1)&m(i-1,j)。  
其中m(i,j)=(Pi == Sj | Pi == ‘.’)  
![在这里插入图片描述][4db8567274be4b14955ebb7f872c20db.png]  
2.缓存并复用以往结果。如图4仍然用二维数组，存的是布尔型。

3.按顺序从小往大算。参考代码。

# 状态转移函数（目标1）
    def f(pattern, i, string, j, results):
        # 当前是星号
        if pattern[i] == '*':
            m_ij = pattern[i - 1] == string[j] or pattern[i - 1] == '.'
            r = results[i - 2][j] | results[i - 1][j] | results[i][j - 1] & m_ij
        # 当前不是星号
        else:
            m_ij = pattern[i] == string[j] or pattern[i] == '.'
            r = results[i - 1][j - 1] & m_ij
        return r
    
    # 主匹配函数
    def is_match(string, pattern):
        # 初始化二维数组（目标2）
        len_string = len(string) + 1  # 给二维数组加哨兵，所以+1
        len_pattern = len(pattern) + 1
        results = [[False] * len_string for i in range(len_pattern)]
        results[0][0] = True
        pattern = '_' + pattern  # 兼容哨兵
        string = '_' + string
    
        # 异常处理
        if len_pattern == len_string == 1:
            return True
        if len_pattern == 1:
            return False
        if pattern[0] == '*':
            return False
    
        # 外循环遍历pattern（目标3）
        for i in range(1, len_pattern):
            # 这里是哨兵处理相关（与星号的情况1相关）
            if pattern[i] == '*':
                results[i][0] = results[i - 2][0]
            # 内循环遍历string（目标3）
            for j in range(1, len_string):
                # 状态转移函数（目标1），以及复用中间结果（目标2）
                results[i][j] = f(pattern, i, string, j, results)
        return results[-1][-1]
    
    if __name__ == '__main__':
        string = "aab"
        pattern = "c*a*b"
        result = is_match(string, pattern) # 结果为true

练习题：https://mp.weixin.qq.com/s/pg-IJ8rA1duIzt5hW1Cycw

[3ee6d1933c7d4e139d4d77e4b51d8ddf.png]: /images/20220828/31c30f682d8743f2b84b1e60ca669bfa.png
[3]: /images/20220828/78a14139e22c4f97acfcca97950e3ea1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbWJzaHFxYg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/fe736cc684a64e50a2660b3b08a99150.png
[4db8567274be4b14955ebb7f872c20db.png]: /images/20220828/4f0d3b0d14fc4402bd442193430acca5.png