动态规划

动态规划问题简称为DP问题（dynamic problem）

1. 规模是否可缩小
2. 用函数思想构造一个状态表达式（黑盒思路）
3. 构造状态转移
4. 优化（memorization/tabulation）

e.g. Longest Common Subsequence(LCS)

1. 规模是否可缩小
2. 用函数思想构造一个状态表达式（黑盒思路）
   • lcs(str1, str2, m, n)
3. 构造状态转移
   • 1+lcs(m-1, n-1)
   • max(lcs(m-1, n), lcs(m, n-1))
4. 优化（memorization/tabulation）
   • overlapping

1 递归树 Recursive Tree

def lcs(str1, str2, m, n):
    if m == 0 or n == 0:
        return 0
    if str1[m-1] == str2[n-1]:
        case1 = 1 + lcs(str1, str2, m-1, n-1)
        return case1
    else:
        case2 = max(lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1))
        return case2

In:

str1 = 'abcdef'
str2 = 'afbce'
m = len(str1)
n = len(str2)
res = lcs(str1, str2, m, n)
print(res)

Out:

4

存在overlapping的问题

2 memoization

改进（自上而下）：

def lcs(str1, str2, m, n):
    #m, n 规模的问题对应的矩阵坐标为m-1, n-1
    if m == 0 or n == 0:
        dp[m][n] = 0
        return 0
    if dp[m][n] != -1:
        return dp[m][n]
    if str1[m-1] == str2[n-1]:
        case1 = 1 + lcs(str1, str2, m-1, n-1)
        dp[m][n] = case1
        return case1
    else:
        case2 = max(lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1))
        dp[m][n] = case2
        return case2

In:

str1 = 'bd'
str2 = 'abcd'
m = len(str1)
n = len(str2)
dp = [[-1] * (n+1) for _ in range(m+1)]
res = lcs(str1, str2, m, n)
print(res)
print(dp)

Out:

2
[[-1, 0, -1, 0, -1], [-1, -1, 1, 1, -1], [-1, -1, -1, -1, 2]]

3 tabulation

改进（自下而上）：

def lcs(str1, str2, m, n):
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            left = dp[i][j-1]
            up = dp[i-1][j]
            left_up = dp[i-1][j-1]
            if str1[i-1] == str2[j-1]:
                dp[i][j] = left_up + 1
            else:
                dp[i][j] = max(left, up)
    #print(dp)
    return dp[m][n]

4 空间优化

4.1 只用两行矩阵

def lcs(str1, str2, m, n):
    dp = [[0] * (n+1) for _ in range(2)]
    #这里发生了变化，只需要两行来推断下面的表格
    for i in range(1, m+1):
        for j in range(1, n+1):
            #代码中的dp[0]代表前一行
            #代码中的dp[1]代表当前行
            left = dp[1][j-1]
            up = dp[0][j]
            left_up = dp[0][j-1]
            if str1[i-1] == str2[j-1]:
                dp[1][j] = left_up + 1
            else:
                dp[1][j] = max(left, up)
        #处理完一行，把当前行的值覆盖前一行
        for k in range(1, n+1):
            dp[0][k] = dp[1][k]
    #print(dp)
    return dp[m][n]

5 小结

	tabulation	memoization
状态转移	不好想	利用递归的思想容易想
代码	需要考虑矩阵的位置关系， 不好写	容易编写
速度	直接通过访问前一个状态的结果计算下一个状态 速度快	多层递归，由于递归的层数在系统中是有限制的，所以有时候会慢，甚至达到限制
表内数据	每一个元素都要填充数据	只有需要的位置才会被填充上数据

下一个状态
速度快 | 多层递归，由于递归的层数在系统中是有限制的，所以有时候会慢，甚至达到限制 |
| 表内数据 | 每一个元素都要填充数据 | 只有需要的位置才会被填充上数据 |