动态规划

发表于 更新于 分类于

动态规划(Dynamic programming，简称DP)，是一种在多学科中常用的复杂问题求解方法，它是一种方法而不是一种算法。它的最基本思想及为将一个问题分解为多个子问题来进行求解。

概述

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。
动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。

重叠子问题

像分治法一样，动态规划包含了对子问题的解决。动态规划主要用于不断地解决相同子问题。在动态规划中，子问题的计算解被存储在表中，使得这些不必重新计算。因此，当没有公共（重叠）子问题时，就不会使用动态规划。例如，二分搜索没有公共子问题。当存在重叠子问题的时候，使用动态规划就能以牺牲少量的空间复杂度来换取时间复杂度的大量减低。比较经典的一个重叠子问题就是斐波那契数列的递归解法。斐波那契数列递归解法与动态规划解法将会在后续的例程例程中出现。

最优子结构

最优子结构是依赖特定问题和子问题的分割方式而成立的条件。如果可以通过各子问题的最优解来求出整个问题的最优解，此时条件成立，认为这是一个最优子结构。反之，如果不能利用子问题的最优解获得整个问题的最优解，那么这种问题就不具有最优子结构。很多问题的最优子结构都表现出非常直观的形式，以至于都不需要另外的证明过程。不过，遇到结构不是很直观的问题时，需要尝试其他的证明方式(反正法等)。

状态转移方程

动态规划中当前的状态往往依赖于前一阶段的状态和前一阶段的决策结果。例如我们知道了第\(i\)个阶段的状态\(S_i\)以及决策\(U_i\)，那么第i+1阶段的状态\(S_{i+1}\)也就确定了。所以解决动态规划问题的关键就是确定状态转移方程，一旦状态转移方程确定了，那么我们就可以根据方程式进行编码。方程可以表示为：
\(S_i = S_{i-1} + U_i\)
根据问题的不同，具体的形式也是多变的，例如最值问题中需要加上\(min和max\)等。

递归递推与记忆化搜索

递归就是从上往下（从n到1），递归过程不记录中间计算所产生的数据，每次需要数据时会一直算到截止条件；递推则是从下往上（从1到n），递推过程记录中间数据，每次需要数据会从记录的数据拿，由于状态方程的关系，递推过程中每次需要的数据一般都会在前面的计算中保留下来；记忆化搜索则是在递归的基础上的改进，它依然是从上往下进行计算，只不过是在计算的时候对数据进行了保留，在需要数据的时候从缓存调取。
递推和记忆化搜索可以说是使用动态规划思路对递归算法的一种改进，都采用了时间换取空间，对于斐波那契数列这个问题来说，可以将时间复杂度从指数级降到一次级。动态规划最常见的实现形式为递推，某些地方不将记忆化搜索视为动态规划方法。

动态规划步骤

1. 划分子问题
2. 确定状态转移方程
3. 自底而上计算最优解
4. 根据所得最优解求解问题

例程详解

斐波那契数列

公元1150年印度数学家Gopala和金月在研究箱子包装对象长宽刚好为1和2的可行方法数目时，首先描述这个数列。在西方，最先研究这个数列的人是比萨的列奥那多（意大利人斐波那契Leonardo Fibonacci），他描述兔子生长的数目时用上了这数列...(不扯了)
斐波那契数列是一个递增的数列，在数学上定义如下： * \(F_0 = 0\) * \(F_1 = 1\) * \(F_n = F_{n-1} + F_{n-2} (n>=2)\)

观察其表达式，可以很简单的写出它的递归形式 

1
2
3
4
5
6
7
def f(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return f(n - 1) + f(n - 2)
使用递归形式来进行计算，对于\(f(n-1)\)\(f(n-2)\)\(f(n-3)\)\(f(n-4)\)......均需要一直递归计算到函数出口，即\(f(1)\)和\(f(2)\)，随着n的增大，计算量将随指数形式增长，时间复杂度为\(O(2^n)\).
如果采用动态规划来计算会怎么样呢。状态转移方程也很简单，直接用递推表达式就可以了：
\(d[i] = d[i-1] + d[i-2]\) 
1
2
3
4
5
6
7
def DP(n):
    dp = [0 for i in range(n + 1)] # 初始化数组
    if n > 0:
        dp[1] = 1                  # 赋初值
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # 递推
    return dp[n]                        # 返回最后的值
可以看到使用动态规划后的时间复杂度为\(O(n)\). ## 路径数量 对于一个矩形区域的格子场地，将其按下表进行编号，从\(0,0\)处开始移动，每次移动只能往左或往右移动一格，求在路径最短的情况下从\(0,0\)移动到\(i,j\)的不同最短路径的数量。

0 1 2 ... j
0 0,0 0,1 0,2 ... 0,j
1 1,0 1,1 1,2 ... 1,j
2 2,0 2,1 2,2 ... 2,j
... ... ... ... ... ...
i i,0 i,1 i,2 ... i,j

既然要求最短路径，则不能移动过程中就不能越界(行超\(i\)或列超\(j\))也不能折返，所以到达\((i，j)\)之前的转态必然是在\((i-1,j)\)或者\((i,j-1)\)，从这两个路径移动到\((i，j)\)也只有一种走法，于是可以得到转态转移方程：
\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)
还需要设定初值：
\(dp[0][0...j] = dp[0...i][0] = 1\)
之后就可以通过递推求解了： 

1
2
3
4
5
6
def DP(row, col):
    dp = np.ones((row + 1, col + 1), dtype=int)
    for i in range(1, row + 1):
        for j in range(1, col + 1):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[row][col]
解决此问题的时间复杂度为\(O(n^2)\).

最长递增子序列

给定一个一维的整数数组，求其中的最长的且严格递增的子序列的长度。
例如对于a = [6,1,7,6,2,5,1,8]，其中最长的且严格递增的为[1,2,5,8]所以长度为4，函数应返回4.
在此处，是否可以将状态\(dp[i]\)定义为\(arr[0]\)至\(arr[i]\)的序列中最长严格单调增子序列的长度呢？咋一看好像没什么问题，往后递推的时候加上\(arr[i+1]\)再计算\(arr[0]\)至\(arr[i+1]\)的单调子序列的长度。可是仔细想想我们无法判断\(arr[i+1]\)加上去之后最长单调增子序列的长度是否增加，因为我们并不知道原先最长的子序列是拿几个，而且这样长度相等的子序列可能不止一个。那这个问题到底能不能使用动态规划来解决呢？当然是可以的。
我们将状态\(dp[i]\)定义为包含元素\(arr[i]\)在内的最长严格递增子序列的长度。这样在求\(dp[i+1]\)的时候，从\(arr[0]\)至\(arr[i]\)中依次寻找比\(arr[i+1]\)小的元素\(arr[j]\)，再从这些元素对应的转态\(dp[j]\)中找到最大(子序列最长)的一个\(max(dp[j])\)，\(dp[i+1]\)的值即为\(max(dp[j])+1\).最大长度子序列是数组\(dp\)中最大的一个值(注意:不一定是最后一个值)。可以写出转态转移方程：
\(dp[i] = max(dp[0]...dp[i-1])+1\)

1
2
3
4
5
6
7
8
9
10
11
def DP(arr):
    dp = [-1 for i in range(len(arr))]
    dp[0] = 1
    for i in range(1, len(arr)):
        max_dp = 0
        for j in range(i):
            if arr[i] > arr[j]:
                if max_dp < dp[j]:
                    max_dp = dp[j]
        dp[i] = max_dp + 1
    return max(dp)
此方法的时间复杂度为\(O(n^2)\).此问题还可以使用贪心加二分查找的方式将时间复杂度降到\(O(nlog(n))\)，此处不再做阐述。

零钱置换

(leetcode.322)
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 * 示例 1： 

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
* 示例 2： 
1
2
输入：coins = [2], amount = 3
输出：-1
* 示例 3： 
1
2
输入：coins = [1], amount = 0
输出：0
* 示例 4： 
1
2
输入：coins = [1], amount = 1
输出：1
* 示例 5： 
1
2
输入：coins = [1], amount = 2
输出：2
我们采用自下而上的方式进行思考。仍定义 \(F(i)\) 为组成金额 \(i\) 所需最少的硬币数量，假设在计算 \(F(i)\) 之前，我们已经计算出 \(F(0)至F(i-1)\)的答案。 则\(F(i)\)对应的转移方程应为:
\(F(i) = min_{j=0...i-1}F(i-c_j)+1\)
其中 \(c_j\)代表的是第 \(j\) 枚硬币的面值，即我们枚举最后一枚硬币面额是 \(c_j\)，那么需要从 \(i-c_j\)这个金额的状态 \(F(i-c_j)\) 转移过来，再算上枚举的这枚硬币数量 1 的贡献，由于要硬币数量最少，所以 \(F(i)\) 为前面能转移过来的状态的最小值加上枚举的硬币数量 1 。

1
2
3
4
5
6
7
8
def DP(coins, amount):
    dp = [float('inf') for i in range(amount + 1)] # 求最小值问题，先把转态都设为无穷大
    dp[0] = 0 # 0元仅需要0个硬币
    for i in range(amount + 1):
        for coin in coins:
            if coin <= i: # i元必定能从i-coin的转态转移过来
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

时间复杂度：\(O(Sn)\)，其中 \(S\) 是金额，\(n\) 是面额数。我们一共需要计算 \(O(S)\) 个状态，\(S\) 为题目所给的总金额。对于每个状态，每次需要枚举 \(n\) 个面额来转移状态，所以一共需要 \(O(Sn)\) 的时间复杂度。