Leetcode 动态规划

Posted on |

动态规划算法

  • 刻画一个最优解的结构特征，利用这种子结构从子问题的最优解构造出原问题的最优解
  • 递归定义最优解的值
  • 计算最优解的值，通常采用自底向上的方法
  • 利用计算的信息构造一个最优解

动态规划的原理

动态规划方法求解的最优化问题必须具备两个要素：最优子结构和子问题重叠。

  • 最优子结构：问题的最优解由相关子问题的最优解组合而成
  • 重叠子问题：子问题空间必须足够小，即问题的递归算法会反复地求解相同地子问题，而不是一致生成新的子问题

动态规划的应用

最优子结构：问题的最优解由相关子问题的最优解组合而成

钢条切割

当完成首次切割后，将两段钢条看作两个独立的钢条切割问题，通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大者。又或者，钢条从左边切割下长度为i的一段，只对右边剩下的n-i的一段继续进行切割

  • 子问题：原问题的最优解只包含一个相关子问题（右端剩余部分）的解
  • 状态转移方程：

对i=1,…,n调用memoized_cut_rod(p,n-i)，等价于对j=0,…,n-1调用memoized_cut_rod(p,j)

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
57
58
59
"""带备忘的自顶向下法 O(n2)"""
def memoized_cut_rod(p,n):
    r=[float('-inf') for i in range(n+1)]   # 收益数组初始化为float('-inf')
    return memoized_cut_rod_aux(p,n,r)

def memoized_cut_rod_aux(p,n,r):
    if r[n]>=0:                         # 先检查值是否已知
        return r[n]
    if n==0:
        q=0
    else:
        q=float('-inf')
        for i in range(1,n+1):
            q=max(q,p[i-1]+memoized_cut_rod_aux(p,n-i,r))
        # for i in range(n):
        #     q=max(q,p[i]+memoized_cut_rod_aux(p,n-i-1,r))
    r[n]=q
    return r[n]

"""自底向上 O(n2)"""
def bottom_up_cut_rod(p,n):
    r=[0]*(n+1)                     # 初始化收益，当n=0，收益为0

    for j in range(1,n+1):          # 按升序求解规模为j的子问题
        q=float('-inf')
        for i in range(1,j+1):      # 每个规模为j的子问题求解和cut_rod相同
            q=max(q,p[i-1]+r[j-i])
        r[j]=q
    return r[n]

def extended_bottom_up_cut_rod(p,n):
    r=[0]*(n+1)                     # 初始化收益，当n=0，收益为0
    s=[0]*(n+1)                     # 保存最优解对应的第一段钢条的切割长度


    for j in range(1,n+1):          # 按升序求解规模为j的子问题
        q=float('-inf')
        for i in range(1,j+1):      # 每个规模为j的子问题求解和cut_rod相同
            if q<p[i-1]+r[j-i]:
                q=p[i-1]+r[j-i]
                s[j]=i
        r[j]=q
    return r,s

def print_cut_rod_solution(p,n):
    r,s=extended_bottom_up_cut_rod(p,n)
    while n>0:
        print(s[n])
        n=n-s[n]

if __name__=='__main__':
    p = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
    n = 4

    # print('cut_rod:\t',cut_rod(p, n))
    print('memoized_cut_rod:\t',memoized_cut_rod(p,n))
    print('bottom_up_cut_rod:\t',bottom_up_cut_rod(p,n))
    print('extended_bottom_up_cut_rod:\t',extended_bottom_up_cut_rod(p,n))
    print('extended_bottom_up_cut_rod:\t',print_cut_rod_solution(p,n))

矩阵链乘法

  • 最优子结构：将问题$A_iA_i+1…A_j$划分为两个子问题（$(A_iA_{i+1}…A_k)$和$(A_{k+1}A_{k+2}…A_j)$的最优括号化问题）。保证在确定分割点是，以考察所有可能的划分点。
  • 递归定义最优解：对$i=1,…,n$确定$A_iA_{i+1}…A_j$的最小代价括号方案作为子问题，$m[i,j]$表示$A_{ij}$所需标量乘法的最小值。则原问题的最优解就是计算$A_{1n}$的最低代价$m[1,n]$.s[i,j]记录最有分割点位置k

$m[i,j]$等于计算$A_{i…k}$和$A_{k+1…j}的代价加上两者相乘的代价的最小值，$k=i,i+1,…,j-1$

最长公共子序列 $O(mn)$

  • 子序列：将给定序列中零个或多个元素去掉之后得到的结果
  • 最优子结构

    递归定义最优解

    如果$x_m=y_n$，需要求解$X_{m-1}$和$Y_{n-1}$的一个LCS。将$x_m=y_n$追加到这个LCS末尾，就得到X和Y的一个LCS。
    如果$x_m \neq y_n$，求解两个子问题：就$X_{m-1}$和Y的一个LCS和X和$Y_{n-1}$的一个LCS。两个LCS较长者几位X和Y的一个LCS。

重叠性：为了求X和Y的LCS，可能需要求X和$Y_{n-1}$的一个LCS以及$X_{m-1}$和Y的一个LCS。但这几个子问题都包含求解$X_{m-1}$和$Y_{n-1}$的LCS的子子问题。

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
def lcs_length(x,y):
    m=len(x)
    n=len(y)
    c=[[0]*(n+1)]*(m+1)
    b=[[0]*n]*m

    for i in range(1,m+1):
        for j in range(1,n+1):
            if x[i-1]==y[j-1]:
                c[i][j]=c[i-1][j-1]+1
                b[i-1][j-1]='lu'
            elif c[i-1][j]>c[i][j-1]:
                c[i][j]=c[i-1][j]
                b[i-1][j-1]=='u'
            else:
                c[i][j]=c[i][j-1]
                b[i-1][j-1]=='l'
    return c,b

def print_lcs(b,x,i,j):
    if i==0 or j==0:
        return
    if b[i-1][j-1]=='lu':
        print_lcs(b,x,i-1,j-1)
        print(x[i-1],end=' ')
    elif b[i-1][j-1]=='u':
        print_lcs(b,x,i-1,j)
    else:
        print_lcs(b,x,i,j-1)

if __name__=='__main__':
    X = ['A', 'B', 'C', 'B', 'D', 'A', 'B']
    Y = ['B', 'D', 'C', 'A', 'B', 'A']
    (c, b) = lcs_length(X, Y)
    print_lcs(b, X, len(X), len(Y))