初识动态规划

Posted on | Post modified: | In
Words count in article: 824 | Reading time ≈ 3

https://mp.weixin.qq.com/s/3h9iqU4rdH3EIy5m6AzXsg
很可爱的漫画。讲的不错，通俗易懂。mark以下，这里就只记一些概念性问题。
动态规划的英文名Dynamic Programming，是一种分阶段求解决问题的数学思想。它不止应用于编程领域，也应用于管理学、经济学、生物学。

它的思想是：大事化小，小事化了
动态规划当中包含三个重要的概念：最优子结构，边界，状态转移公式
通过下面漫画提到的题目对三个概念阐述。
在这里插入图片描述 在最后一级台阶，由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)是阶段与阶段之间的状态转移方程。这是动态规划的核心，决定了问题的每一个阶段和下一个阶段的关系。
其实分析到这里后，和漫画里的小灰一样，我的第一反应也是用递归做，毕竟递归方程和边界都给出了。
下面给出递归的代码：

1
2
3
4
5
6
7
def dp(n):
    if n <= 0:
        return 0
    elif n == 1 or n == 2:
        return n
    else:
        return dp(n-1) + dp(n-2)

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

1
2
3
4
5
6
7
8
9
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)。
上面的两种实现方法都是自顶向下递归实现的，因此也就无法利用之前计算的结果。因为本题归纳的公式，我们可以看出如果自低向上迭代运算，在下一次运算可以用到上次运算的结果。每一次迭代过程中，只要保留之前的两个状态，就可以推导出新的状态。这就是动态规划。

1
2
3
4
5
6
7
8
9
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
------ 本文结束 ------
0%