算法学习笔记：动态规划

动态规划（dynamic programing）是用来解决最优化问题的一类算法。

在数学上，最优化问题是指从所有可行解中找到最优解，使得目标函数的值最大或最小。在广义的最优化问题中，可行解可以是连续或离散的，是有约束或无约束的，目标函数可以是线性或非线性的。本文只讨论一类特定的最优化问题，这类问题的解通常是离散且有约束的（从某个有限离散集合中选出特定子集，例如从序列中选出子序列），目标函数通常为线性的（例如序列长度，集合求和）。

动态规划的思想

无论是动态规划还是线性规划，“规划”一词都是指利用表格来求解。线性规划中的单纯型算法利用“单纯型表”求解，而动态规划算法则是利用“记忆化表”来求解。动态规划中的表格用于存储子问题的答案，当算法再次求解子问题时就可以直接从表格中获得答案，这样可以大大降低算法的时间复杂度。

最长公共子序列

给定两个序列[a1,...,an]和序列[b1,...,bm]，求它们的最长公共子序列。例如若序列为字符串，则abc是abcdaf的子序列，也是acbcf的子序列，因此abc是它们的公共子序列，而abcf是它们的最长公共子序列，长度为4。

一种显而易见的算法是穷举各自的所有子序列，然后找出其中的公共子序列，最后从中找出最长的子序列。显然这种算法的复杂度非常高。

简单递归算法

首先，尝试使用递归来解决这个最优化问题，下面是递归算法的伪代码：

1
2
3
4
5


设 T(i,j)为序列[a1,...,ai]和序列[b1,..,bj]的最长公共子序列长度；
计算 T(i,j)的算法如下：
    1. 如果 i 或 j 等于 0，那么其中一个序列为空，则 T(i,j) = 0；
    2. 如果 i,j 不等于 0，且 ai 等于 bj，那么先计算出 T(i-1)T(j-1)，则 T(i,j) = T(i-1)(j-1) + 1；
    3. 如果 i,j 不等于 0，且 ai 不等于 bj,那么先计算出 T(i-1,j)和 T(i,j-1)，则 T(i,j) = max(T(i-1,j), T(i,j-1))

可以看出，这个算法的效率很低，关键在于其中许多重复的计算。例如，计算T(5,5)需要递归计算T(4,5)和T(5,4)，而计算T(4,5)和T(5,4)都需要递归计算T(4,4)，因此T(4,4)进行了重复计算。

记忆化

显然，我们可以对上面的算法进行优化，优化的方法是对重复计算的结果进行记忆，下一次需要计算结果时直接从记忆中取，以此节省计算时间。这种技术称为记忆化（memoization），可以认为是动态规划的关键技术。

记忆化通常使用一个数组来存储计算结果。例如，对于上面的递归算法，我们可以用一个n行m列的二维数组T[n][m]来存储T(i,j), i in [0,n], j in [0,m]的结果，初始时T[i][j]为空。当需要计算T(i,j)时，首先从数组中读取T[i][j]。如果结果为空，说明之前没有计算过T(i,j)，那么就先计算T(i,j)，然后把结果存入T[i][j];如果结果不为空，说明之前已经计算过T(i,j)，那么可以直接返回结果。

自顶向下和自底向上

上面的算法在计算T(i,j)时递归调用了T(i-1,j-1)，函数的参数在递归中不断减小，这种方式称为自顶向下的递归算法，因为函数的调用顺序是自顶向下的。

然而从上面的算法可以看出，T[i][j]的值依赖于T[i-1][j-1]，T[i-1][j]和T[i][j-1]的值。如果我们观察T[i][j]的写入顺序的话，我们会发现T[i][j]总是在T[i-1][j-1]，T[i-1][j]和T[i][j-1]之后写入的，这说明，函数的计算顺序实际上是自底向上的。所以上面的递归算法也可以改写成自底向上的迭代算法。

无论是自顶向下算法，还是自底向上算法，算法的最终目的就是计算T(i,j)的值，在上面的算法中就是得到表中T[n][m]的值。可以说，动态规划的算法核心就是填表。由表T的依赖关系可以看出，表T中的每一个值都依赖于它上边，左边和左上的值。由于T[n][m]位于表的最右下角，所以要想得到T[n][m]的值，就需要先填入表T中所有的其他值。

因此，如果我们使用自底向上的迭代算法，那么根据依赖关系，我们可以有许多不同计算的顺序，只需要保证在填表的每一个格时，当前格的依赖值已经填入表中。例如在上面的算法中，表T中的值依赖于它上边，左边和左上的值，因此我们计算T[i][j]时，只要保证T[i-1][j]，T[i][j-1]，T[i-1][j-1]已经填入表中即可。于是我们的计算顺序可以有许多种：既可以逐行从左到右，从上到下；也可以逐列从上到下，从左到右。在实际的编程中我们可以根据依赖关系，自由选择当前合适的顺序来填表。下面的代码使用了逐行的迭代算法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def LCS(s1, s2):
    len1, len2 = len(s1), len(s2)
    T = [[0] * (len2+1) for _ in range(len1+1)]

    for i in range(1, len1+1):
        for j in range(1, len2+1):
            if s1[i-1] == s2[j-1]:
                T[i][j] = 1 + T[i-1][j-1]
            else:
                T[i][j] = max(T[i-1][j], T[i][j-1])

    return T[len1][len2]

构造解

目前，T(n,m)只是计算出了最长公共子序列的长度，但是没有给出相应子序列的具体值。也就是说，目前我们只得到了最优化问题的目标函数的最优值，但没有给出相应的最优解。下面我们就通过表T中的信息来还原出最优解。

从上面的算法中我们知道，如果ai == bi，那么T(i,j) == T(i-1,j-1)，此时ai就是序列[a1,...,ai]和序列[b1,...,bi]最长公共子序列中的最后一个元素。于是我们可以用下面的算法从表T中还原出最优解ans：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def get_solution(T, len1, len2):
    i, j = len1, len2
    ans = []
    while i > 0 and j > 0:
        if T[i][j] == T[i][j-1]:
            j = j - 1
        elif T[i][j] == T[i-1][j]:
            i = i - 1
        else:
            ans.append(s1[i-1])
            i, j = i - 1, j - 1
    return ans[::-1]

算法优化

此外，上面的算法还可以进行更深入的优化。可以看出在，逐行迭代算法中，表中的每一行的值都只依赖上一行的值，因此表T实际只需要2行即可，算法的空间复杂度就从$O(nm)$降到了$O(n)$，但此时的表T不能还原出最优解。

动态规划求解的步骤

定义子问题
写出递推式
转化为迭代算法
算法优化

与贪心算法的关系

都具有最优子结构，问题的最优解包含了其子问题的最优解；
贪心算法具有贪心性质，局部的最优解一定属于全局最优解；
动态规划求解的方向是自底向上，而贪心算法求解的方向是自顶向下。动态规划先对子问题进行求解，然后再从所有子问题的解中得出某个最优的选择；然而贪心算法先得出一个目前最优的选择，然后再求解留下的子问题。所以动态规划是先求解后做选择，而贪心算法是先做选择后求解。因此贪心算法不需要对每个子问题进行求解，每次只需要求解一个子问题。

相关问题解法

01 背包问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


def knapsack(W, weight, value):
    n = len(weight)
    T = [[0] * (W+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(W+1):
            if weight[i-1] > j:
                # 背包放不下，不选
                T[i][j] = T[i-1][j]
            else:
                # 背包放得下，选不选取决于哪种价值更大
                T[i][j] = max(value[i-1] + T[i-1][j-weight[i-1]],
                              T[i-1][j])
    # 获取选择的物品编号
    choice = []
    i, j = n, W
    while i > 0 and j > 0:
        if T[i][j] != T[i-1][j]:
            choice.append(i-1)
            j = j - weight[i-1]
        i = i - 1
    return T[n][W], choice[::-1]

if __name__ == '__main__':
    print(knapsack(7,[1,3,4,5],[1,4,5,9]))

时间复杂度 $O(nW)$

最长公共子序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


def LCS(s1, s2):
    len1, len2 = len(s1), len(s2)
    T = [[0] * (len2+1) for _ in range(len1+1)]

    for i in range(1, len1+1):
        for j in range(1, len2+1):
            if s1[i-1] == s2[j-1]:
                T[i][j] = 1 + T[i-1][j-1]
            else:
                T[i][j] = max(T[i-1][j], T[i][j-1])

    # 构造解
    i, j = len1, len2
    ans = []
    while i > 0 and j > 0:
        if T[i][j] == T[i][j-1]:
            j = j - 1
        elif T[i][j] == T[i-1][j]:
            i = i - 1
        else:
            ans.append(s1[i-1])
            i, j = i - 1, j - 1
    return T[len1][len2], ''.join(ans[::-1])

if __name__ == '__main__':
    print(LCS('abcdaf', 'acbcf'))

矩阵链乘

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


def matrix_mul_cost(mat_shapes):
    import sys

    length = len(mat_shapes)
    T = [[0] * (length) for _ in range(length)]
    S = [[0] * (length) for _ in range(length)]

    for l in range(1,length):
        for i in range(length-l):
            j = i + l
            ans = sys.maxsize
            for k in range(i, j):
                tmp = T[i][k] + T[k+1][j] + mat_shapes[i][0]*mat_shapes[k][1]*mat_shapes[j][1]
                if tmp < ans:
                    ans = tmp
                    s = k
            T[i][j] = ans
            S[i][j] = s

    # 递归构造解
    def get_solution(i, j):
        if i == j:
            return i
        else:
            left = get_solution(i, S[i][j])
            right = get_solution(S[i][j]+1, j)
            return (left, right)

    return T[0][length-1], get_solution(0, length-1)

if __name__ == '__main__':
    print(matrix_mul_cost([(2,3),(3,6),(6,4),(4,5)]))

子集和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


def subset_sum(nums, total):
    n = len(nums)
    T = [[True]+[False] * total for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, total+1):
            if nums[i-1] > j:
                T[i][j] = T[i-1][j]
            else:
                T[i][j] = T[i-1][j] or T[i-1][j-nums[i-1]]

    ans = []
    if T[n][total]:
        i, j = n, total
        while i > 0 and j > 0:
            if not T[i-1][j]:
                ans.append(nums[i-1])
                j = j - nums[i-1]
            i = i - 1

    return T[n][total], ans[::-1]

if __name__ == '__main__':
    print(subset_sum([2,3,7,8,10], 11))

最优二叉搜索树

下面的算法复杂度为$O(n^3)$，可优化至$O(n^2)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def optimal_bst(keys, times):
    import sys
    n = len(keys)
    T = [[0] * n for _ in range(n)]
    S = [[0] * n for _ in range(n-1)]
    for i in range(0, n):
        T[i][i] = times[i]

    for l in range(1, n):
        for i in range(0, n-l):
            j = i + l
            ans = sys.maxsize
            for k in range(i, j+1):
                left = 0 if k-1 < i else T[i][k-1]
                right = 0 if k+1 > j else T[k+1][j]
                tmp = sum(times[i:j+1]) + left + right
                if tmp < ans:
                    ans = tmp
                    s = k
            T[i][j] = ans
            S[i][j] = s

    def get_solution(i, j):
        if i == j:
            return Node(keys[i])
        elif i > j:
            return None
        else:
            k = S[i][j]
            root = Node(keys[k])
            root.left = get_solution(i, k-1)
            root.right = get_solution(k+1, j)
            return root

    return T[0][n-1], get_solution(0, n-1)

if __name__ == '__main__':
    total, root = optimal_bst([1,2,3,4], [4,2,6,3])
    def preorder(root):
        ans = []
        def helper(root):
            if root == None:
                return
            else:
                ans.append(root.data)
                helper(root.left)
                helper(root.right)
        helper(root)
        return ans
    print(total, preorder(root))

最小硬币找零

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


def coin_changing(coins, total):
    import sys
    T = [sys.maxsize] * (total+1)
    T[0] = 0
    S = [-1] * (total + 1)
    for i, c in enumerate(coins):
        for j in range(1, total+1):
            if c <= j and 1 + T[j-c] < T[j]:
                T[j] = 1 + T[j-c]
                S[j] = i
    ans = []
    if S[total] != -1:
        j = total
        while j > 0:
            c = coins[S[j]]
            ans.append(c)
            j = j - c
        return T[total], ans
    else:
        return False, ans

if __name__ == '__main__':
    print(coin_changing([3,2,4], 11))

最小编辑距离

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


def min_edit_distance(s1, s2):
    n1 = len(s1)
    n2 = len(s2)
    T = [[None] * (n1+1) for _ in range(n2+1)]
    for i in range(n1+1):
        T[0][i] = i
    for i in range(n2+1):
        T[i][0] = i

    for i in range(n2):
        for j in range(n1):
            if s1[j] == s2[i]:
                T[i+1][j+1] = T[i][j]
            else:
                T[i+1][j+1] = 1 + min(T[i][j], T[i+1][j], T[i][j+1])

    i, j = n2, n1
    ans = []
    while i > 0 and j > 0:
        if s1[j-1] == s2[i-1]:
            i, j = i-1, j-1
        elif T[i][j] == 1 + T[i-1][j]:
            i = i - 1
            ans.append((i, s2[i]))
        elif T[i][j] == 1 + T[i][j-1]:
            j = j - 1
            ans.append((s1[j], None))
        else:
            i, j = i-1, j-1
            ans.append((s1[j], s2[i]))

    return T[n2][n1], ans[::-1]


if __name__ == '__main__':
    print(min_edit_distance('abcdef', 'abccde'))

最长递增序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


def longest_incresing_sub(nums):

    def binary_search(arr, x):
        i, j = 0, len(arr)
        while i < j:
            p = (i + j) // 2
            if nums[arr[p]] < x:
                i = p + 1
            elif nums[arr[p]] > x:
                j = p
            else:
                return p
        return i

    n = len(nums)
    T = [0]
    S = [-1] * n
    l = 1
    for i in range(1, n):
        x = nums[i]
        if x > nums[T[-1]]:
            l = l + 1
            S[i] = T[-1]
            T.append(i)
        elif x < nums[T[0]]:
            T[0] = i
        else:
            j = binary_search(T, x)
            T[j] = i
            S[i] = T[j-1]

    i = T[-1]
    ans = [nums[i]]
    while S[i] != -1:
        ans.append(nums[S[i]])
        i = S[i]
    return l, ans[::-1]


if __name__ == '__main__':
    print(longest_incresing_sub([3,4,-1,5,9,2,3,12,7,9,10]))

最长回文序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


def longest_palindrome_sub(arr):
    n = len(arr)
    T = [[0] * n for _ in range(n)]
    for i in range(n):
        T[i][i] = 1

    for l in range(1, n):
        for i in range(n-l):
            j = i + l
            if arr[i] == arr[j]:
                T[i][j] = T[i+1][j-1] + 2
            else:
                T[i][j] = max(T[i+1][j], T[i][j-1])

    i, j = 0, n-1
    ans = []
    while i <= j:
        if T[i][j] == T[i+1][j]:
            i = i + 1
        elif T[i][j] == T[i][j-1]:
            j = j - 1
        else:
            ans.append(arr[i])
            i, j = i+1, j-1
    ans = ans + ans[-2::-1]

    return T[0][n-1], ''.join(ans)


if __name__ == '__main__':
    print(longest_palindrome_sub('agbdba'))

硬币找零方法数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


def coin_changing_ways(coins, total):
    n = len(coins)
    T = [[1]+[0]*total for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, total+1):
            if j < coins[i-1]:
                T[i][j] = T[i-1][j]
            else:
                T[i][j] = T[i-1][j] + T[i][j-coins[i-1]]
    return T[n][total]


if __name__ == '__main__':
   print(coin_changing_ways([1,2,3],5))

文章目录

动态规划的思想

最长公共子序列

简单递归算法

记忆化

自顶向下和自底向上

构造解

算法优化

动态规划求解的步骤

与贪心算法的关系

相关问题解法

01 背包问题

最长公共子序列

矩阵链乘

子集和

最优二叉搜索树

最小硬币找零

最小编辑距离

最长递增序列

最长回文序列

硬币找零方法数