初识动态规划

旧城等待， 2022-02-01 10:51 221阅读 0赞

[https://mp.weixin.qq.com/s/3h9iqU4rdH3EIy5m6AzXsg][https_mp.weixin.qq.com_s_3h9iqU4rdH3EIy5m6AzXsg]  
很可爱的漫画。讲的不错，通俗易懂。mark以下，这里就只记一些概念性问题。  
动态规划的英文名Dynamic Programming，是一种分阶段求解决问题的数学思想。它不止应用于编程领域，也应用于管理学、经济学、生物学。  
它的思想是：**大事化小，小事化了**  
动态规划当中包含三个重要的概念：**最优子结构**，**边界**，**状态转移公式**  
通过下面漫画提到的题目对三个概念阐述。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoZXJpc2hfeA_size_16_color_FFFFFF_t_70] 在最后一级台阶，由2种走法，第一种：从第九级台阶跨一步到达第十级台阶；第二种：从第八级台阶跨2步到达第十级台阶。那是不是说，到达第十级台阶的走法有多少种，是由到达第八级台阶和到底第九级台阶的走法之和决定的呢？  
当然是的。  
因此，可以以此类推，直到第一级台阶或者第二级台阶。  
用公式简化过程：  
f(n)表示到达第n级台阶的走法，由上面分析，有  
f(10) = f(9) + f(8)  
f(9) = f(8) + f(7)  
。。。  
f(3) = f(2) + f(1)  
归纳：  
f(1) = 1  
f(2) = 2  
f(n) = f(n-1) + f(n-2) (n>=3)  
刚才分析出f(10) = f(9) + f(8)，因此f(9)和f(8)是f(10)的**最优子结构**  
当只用一级台阶或2级台阶的时候，我们可以直接得出结果，无需继续简化。我们成f(1)和f(2)为问题**边界**。如果一个问题没有边界，将永远无法得到有限的结果。  
f(n) = f(n-1) + f(n-2)是阶段与阶段之间的**状态转移方程**。这是动态规划的核心，决定了问题的每一个阶段和下一个阶段的关系。  
其实分析到这里后，和漫画里的小灰一样，我的第一反应也是用递归做，毕竟递归方程和边界都给出了。  
下面给出递归的代码：

def dp(n):
        if n <= 0:
            return 0
        elif n == 1 or n == 2:
            return n
        else:
            return dp(n-1) + dp(n-2)

但是递归的时间复杂度有点高。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoZXJpc2hfeA_size_16_color_FFFFFF_t_70 1]  
差不多应该是O(2^n)。  
从上图可以看出有些数据被重复计算了，那么我们可将这些数据缓存下来。  
下面用**备忘录算法**优化一下。

hashMap = { }
    def dp(n, hashMap):
        if n == 1 or n == 2:
            return n
        elif n in hashMap:
            return hashMap[n]
        else:
            hashMap[n] = dp(n-1, hashMap) + dp(n-2, hashMap)
            return hashMap[n]

这样时间复杂度就降到了O(n)，但是空间复杂度也就变成了O(n)。  
上面的两种实现方法都是自顶向下递归实现的，因此也就无法利用之前计算的结果。因为本题归纳的公式，我们可以看出如果自低向上迭代运算，在下一次运算可以用到上次运算的结果。每一次迭代过程中，只要保留之前的两个状态，就可以推导出新的状态。这就是动态规划。

def dp(n):
        if n <= 0:
            return 0
        elif n == 1 or n == 2:
            return n
        f1, f2 = 1, 2
        for i in range(3, n+1):
            f1, f2 = f2, f1 + f2
        return f2

[https_mp.weixin.qq.com_s_3h9iqU4rdH3EIy5m6AzXsg]: https://mp.weixin.qq.com/s/3h9iqU4rdH3EIy5m6AzXsg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoZXJpc2hfeA_size_16_color_FFFFFF_t_70]: /images/20220201/ebd4258e6af64094a6e845de47ec9640.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoZXJpc2hfeA_size_16_color_FFFFFF_t_70 1]: /images/20220201/8cf233f65c014766a01689ce8346c74b.png