图解动态规划

总结自：10 分钟彻底搞懂“动态规划”算法

下面用实例讲解什么是动态规划算法（Dynamic Programming，DP）。

首先我们来看一个经典的动态规划问题。

输入一个无序的数组，要求找出其中最长的递增的子序列。

如：对于[1, 5, 2, 4, 3]，其最长递增子序列为1,2,4、1,2,3。

但这里我们对这个问题进行简化，我们只要求返回最长递增子序列的长度即可。对于[1, 5, 2, 4, 3]，最长递增子序列的长度为3。

暴力搜索

最容易想到的解法是暴力搜索。比如从1出发，下一个数字可以是5、2、4或者3，因为它们都是递增的：

假如下一个数字我们取5的话，再下一个数字都取不了，因为剩下的2，4，3都比5小，不能够构成一个递增序列：

如果下一个数字是2的话，下一个数字可以是4或3，此时构成的递增序列长度为3：

以此类推，如果下一个数字我们取4，下一个数字依然不能选，因为3比4小：

算法就这样循环往复地执行，直到遍历完所有以1开头的子序列，并且在遍历过程中，我们会实时记录当前的最长递增子序列长度：

最后可以知道，从1出发，最长的递增子序列长度为3：

我们按照同样的方法计算从5、2、4和3出发的最长递增子序列长度：

得到max_len数组，选出最长的那个，即取max_len数组的最大值，算法结束：

要实现上述算法，我们可以定义函数L(nums, i)，该函数返回从数组nums的第i个数字开始的最长子序列长度：

def L(nums, i):
    """Returns the length of longest increasing subsequence starting from i"""

[ 1, 5, 2, 4, 3 ]
  ↑
  i

在函数L中，我们检查i后面的所有数字（数字索引标记为j），只要该数字比i位置的数大，那么以i开始的最长递增子序列长度就等于以j开始的最长递增子序列长度加1，求以j开始的最长递增子序列长度也执行这个过程，所以我们递归地调用L函数：

def L(nums, i):
    """Returns the length of longest increasing subsequence starting from i"""
    if i == len(nums) - 1: # last number
        return 1
    max_len = 1
    for j in range(i, len(nums)):
        if nums[j] > nums[i]:
            max_len = L(nums, j) + 1
    return max_len

使用L函数，求从各位置开始的最长递增子序列长度，并取最大值，即可得到最长递增子序列的长度：

"""longest increasing subsequence"""
def LIS(nums):
    return max(L(nums, i) for i in range(len(nums)))

这个算法的问题是，它的时间复杂度不可接受，假设数组长度为 n，那么其子序列个数为 2ⁿ，每个子序列最多遍历 n 次，所以时间复杂度为 O(2ⁿ) * O(n) = O(n * 2ⁿ)。

优化

观察遍历树，会发现其中存在大量重复计算：

比如我们遍历子序列1,2,4的时候就已经计算过“从 4 开始的最大子序列的长度”：

后面遍历1,4的时候又重复计算了一次：

为了避免重复的计算，我们可以在第一次计算的时候，将结果保存起来：

后遍历到相同的节点我们就不再需要再重复计算了，直接将之前的结果返回：

代码如下：

memo = {} # 用于记录计算结果

def L(nums, i):
    if i in memo:
        return memo[i] # 如果已经计算过，则直接返回
    if i == len(nums) - 1:
        return 1
    max_len = 1
    for j in range(i, len(nums)):
        if nums[j] > nums[i]:
            max_len = L(nums, j) + 1
    memo[i] = max_len # 记录结果
    return max_len

def LIS(nums):
    return max(L(nums, i) for i in range(len(nums)))

由于用到了字典/哈希表来保存计算的中间结果，因此我们也称之为“记忆化”搜索（Recursion With Memoization），有人也称其为带“备忘录”的递归，或者叫递归树的“剪枝”（Pruning）。

迭代的形式

由于1可以和5、2、4、3构成递增序列，所以要计算从1开始的最长子序列长度，可以先计算从5、2、4、3开始的最长子序列长度：

取其中的最大值，然后加一：

同样地，要计算从5开始最长子序列长度，先找到之后比5大的数，计算各数的最长子序列长度，取其中的最大值，再加一：

这里没有比5大的数，结果为1：

以此类推，直到最后一个数（最长递增子序列长度为 1）：

从右侧的公式可以知道，只要从后往前依次计算，就可以将所有答案推算出来：

具体实现用到了两个循环，外面的循环表示从下往上依次计算：

里面的循环用于遍历括号中的这些数值：

运算的结果用数组L存放：

对于后面的比当前数大的所有数（能构成递增序列的数），在L[i]和L[j]+1中取较大值更新到L[i]，效果等价于先找到后面比当前数大的数，计算各数的最长子序列长度并取其中的最大值保存到L[i]：

最后返回L数组中的最大值：

代码实现：

def length_of_LIS(nums):
    n = len(nums)  # 5
    L = [1] * n # initial value: [1,1,1,1,1]
    
    for i in reversed(range(n)):  # i -> 4,3,2,1,0
        for j in range(i + 1, n):
            if nums[j] > nums[i]: # is increasing seq
                L[i] = max(L[i], L[j] + 1)
                
    return max(L)

其中有两个循环，每个循环最多执行 N 次，时间复杂度 O(n²)。

一般思路

穷举法 / 暴力搜索

使用动态规划解决问题，可以先考虑用暴力穷举的方法解决，并画出递归树，尝试写一个递归函数来求解。

记忆化搜索 / 剪枝

如果发现遍历中存在大量的重复计算，可以尝试用哈希表将数据缓存下来，之后遍历到相同的节点就直接查表，避免重复的计算。

改写成迭代形式

最后，可以将计算的过程表示出来，然后观察公式求解的顺序，并尝试将递归形式改写成更加高效的迭代形式。