数据结构与算法基础——动态规划（Dynamic programming）

  |   0 评论   |   942 浏览

基础概念

最优子结构

如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

无后效性

即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

重叠子问题

子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

备忘录/空间换时间

在递归求解问题时，往往会对同一个子问题反复求解，这样会造成时间复杂度的增加，为了减少重复计算，可以利用一个哈希表暂存中间子问题的解，这样在后续计算时可以先检查缓存，如果已经计算过，就不必再次计算。

状态

计算机的本质是一个状态机，内存里存储的所有数据构成了当前的状态，CPU只能利用当前的状态计算出下一个状态（不要纠结硬盘之类的外部存储，就算考虑他们也只是扩大了状态的存储容量而已，并不能改变下一个状态只能从当前状态计算出来这一条铁律）

当你企图使用计算机解决一个问题时，其实就是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据）以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少，所谓时间复杂度就是从初始状态到达最终状态中间需要多少步！

一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的！

  1. 每个阶段只有一个状态->递推

  2. 每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心

  3. 每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索

  4. 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划

状态转移方程

状态和状态之间的关系式，就叫做状态转移方程。描述了原问题的解如何由子问题的解组合而成

动态规划

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划的本质，是对问题状态的定义和状态转移方程的定义。

三个特点

  1. 把原来的问题分解成了几个相似的子问题。（强调“相似子问题”）

  2. 所有的子问题都只需要解决一次。（强调“只解决一次”）

  3. 储存子问题的解。（强调“储存”）

动态规划的实现方法

“自顶向下”（top-down dynamic programming）

  1. 能方便的得到递归公式，并用递归函数实现

  2. 保持了递归实现的代码结构，逻辑上容易理解。

  3. 过程中只计算需要计算的子结果。

  4. 当采用了caching技术时多次被调用时天然的复用之前被调用时的子结果。（比如连续两次计算fibonacci数F(4), F(5),则计算F(5)时已知F(3)和F(4)，直接相加即可）

“自低向上”（bottom-up dynamic programming）

  1. 需要设计数据结构来完成自底向上的计算过程。逻辑上相对不那么直观。

  2. 常常可以进行空间复杂度的优化。比如Fibonacci数列可以优化为只使用两个变量的额外存储空间，0-1背包问题可以优化为O(n)的空间复杂度。

  3. 若进行了空间优化，则连续多次被调用时无法复用之前被调用的子结果。

分析

  1. 状态是什么

  2. 状态转移方程是什么

  3. 状态的初始值是什么

  4. 问题要求的最后答案是什么

解题步骤

  1. 描述最优解的结构

  2. 递归定义最优解的值

  3. 按自底向上的方式计算最优解的值

  4. 由计算出的结果构造一个最优解

斐波那契数列（Fibonacci polynomial）

计算斐波那契数列（Fibonacci polynomial）的一个最基础的算法

其状态转移方程为

f(n) = f(n - 1) + f(n - 2)

自顶向下的函数递归方式

#! /usr/bin/python
# -*- coding:utf-8 -*-
def fib(n):
    if n == 0 or n == 1:
        return n
    print '计算: fib(%d)' % n
    return fib(n - 1) + fib(n - 2)
if __name__ == "__main__":
    print fib(5)

输出

计算: fib(5)
计算: fib(4)
计算: fib(3)
计算: fib(2)
计算: fib(2)
计算: fib(3)
计算: fib(2)
5

由上面可以看出，这种算法对于相似的子问题进行了重复的计算，因此不是一种高效的算法。实际上，该算法的运算时间是指数级增长的。 改进的方法是，我们可以通过保存已经算出的子问题的解来避免重复计算：

#! /usr/bin/python
# -*- coding:utf-8 -*-
dp = {}
def fib(n):
    if dp.get(n, None) != None:
        return dp[n]
    if n == 0 or n == 1:
        return n
    print '计算: fib(%d)' % n
    v = fib(n - 1) + fib(n - 2);
    dp[n] = v
    return v
if __name__ == "__main__":
    print fib(5)

对比输出

计算: fib(5)
计算: fib(4)
计算: fib(3)
计算: fib(2)
5

自底向上的动态规划的解法

上面的解法空间复杂度较高，仔细分析发现，我们并不需要存储所有的结果，每个值只与其前两个值相关，因此我们只需要存储其前两个值即可

#! /usr/bin/python
# -*- coding:utf-8 -*-
def fib(n):
    fib_n_1 = 0
    fib_n_2 = 1
    i = 0
    while (i < n):
        i += 1
        if i == 1:
            continue
        print '计算: fib(%d)' % i
        v = fib_n_1 + fib_n_2
        # 交换变量
        fib_n_2 = fib_n_1
        fib_n_1 = v
    return fib_n_1 + fib_n_2
if __name__ == "__main__":
    print fib(5)


输出

计算: fib(2)
计算: fib(3)
计算: fib(4)
计算: fib(5)
5

与其他算法的关联

动态规划与贪心算法的区别

动态规划以自底向上的方式来利用最优子结构。也就是说，首先找到子问题的最优解，解决的子问题，然后找到问题的一个最优解。寻找问题的一个最优解需要首先在子问题中做出选择，即选择用哪一个来求解问题。问题解的代价通常是子问题的代价加上选择本身带来的开销。

在贪心算法中是以自顶向下的方式使用最优子结构。贪心算法会先做选择，在当时看来是最优的选择，然后在求解一个结果子问题，而不是现寻找子问题的最优解，然后再做选择。

与分治法的区别

分治法是将问题分解为一些独立的子问题，递归的求解各个子问题，然后合并子问题的解而得到源问题的解。

而动态规划适合用于子问题不是独立的情况，也就是各个子问题包含公共的子子问题。在这种情况下，若采用分治的的思想则会做许多不必要的工作。动态规划会对每个子子问题之求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。