数据结构与算法【Python实现】（九）动态规划

2022-01-11 02:03:30

一、斐波那契数列

Fn =Fn-1 + Fn-2

#子问题的重新计算
def fabnacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fabnacci(n-1)+fabnacci(n-2)

#非递归算法：动态规划思想DP
def fabnacci_no_rec(n):
    f = [0,1,1]
    if n >= 2:
        for i in range(n-2):
            num = f[-1]+f[-2]
            f.append(num)
        return f[n]

动态规划：最优子结构→递归式

二、钢条切割问题

1、自顶向下递归实现

某公司出售钢条，出售价格与钢条长度之间的关系如下表：

现有一段长度为n的钢条和上面的价格表，求切割钢条方案，使总收益最大

长度为n的钢条有 2^(n-1)种切割方案

（1）递推式：

设长度为n的钢条最优收益为r_n，递推式为

r_n = max(p_n, r_1+r_n-1, r_2+r_n-2, r_3+r_n-3……, r_n-1+r_1)

p_n表示不切割

其他n-1个参数分别表示另外n-1种不同切割方案，对方案 i=1,2…,n-1：

将钢条分为长度为 i 和n-i两段

方案 i 的收益为切割两段的最有收益之和

考察所有的 i ，选择其中收益最大的方案

（2）简化递推式：

从钢条的左边切割下长度为 i 的一段，只对右边剩下的一段继续进行切割，左边的不再切割

递推式简化为：r_n = max(p_i + r_n-1) 1 <= i <= n-i

print(cut_rad_rec_1(p,9))

不做切割的方案可以描述为：左边一段长度为n，收益为p_n，剩余一段长度为0，收益为r_0=0

最优子结构：

可以将求解规模为n的原问题，划分为规模更小的子问题：完成一次切割后，可以将产生的两段钢条看成两个独立的钢条切割问题。

组合两个子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大的，构成原问题的最优解。

钢条切割问题满足最优子结构：问题的最优解由相关子问题的最优解组合而成，这些子问题可以独立求解。

方法一：简化前写法

p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

def cut_rod_rec_1(p, n):
    if n== 0:
        return 0
    else:
        res = p[n]
        for i in range(1,n):
            res = max(res, cut_rod_rec_1(p,i) + cut_rod_rec_1(p,n-i))
        return res

print(cut_rod_rec_1(p,9))

方法二：简化后写法

def cut_rod_rec_2(p, n):
    if n == 0:
        return 0
    else:
        res = 0
        for i in range(1,n+1):
            res = max(res, p[i] + cut_rod_rec_2(p,n-i))
        return res

速度更快

自顶向下递归实现效率差：时间复杂度 O(2^n)

2、动态规划解法——自底向上实现

递归算法由于重复求解相同子问题，效率极低

动态规划的思想：

每个子问题只求解一次，保存求解结果

之后需要此问题时，只需查找保存的结果

先算r_1, 存起来，再算r_2……

def cut_rod_dp(p, n):
    r = [0]
    for i in range(1, n+1):
        res = 0
        for j in range(1, i+1):
            res = max(res, p[j] + r[i-j])
        r.append(res)
    return r[n]

时间复杂度 O(n^2)

3、重构解

如何输出最优切割方案？

——对于每个子问题，保存切割一次时左边切下的长度

def cut_rod_extend(p, n):
    r = [0]
    s = [0]
    for i in range(1, n+1):
        res_r = 0  #记录价格最大值
        res_s = 0  #记录最优切割处
        for j in range(1, i+1):
            if p[j] + r[i-j] > res_r:
                res_r = p[j] + r[i-j]
                res_s = j
        r.append(res_r)
        s.append(res_s)
    return r[n], s

def cut_rod_solution(p, n):
    r, s = cut_rod_extend(p, n)
    ans = [] #存放最终切割方案
    while n > 0:
        ans.append(s[n])
        n -= s[n]
    return r, ans

什么问题可以使用动态规划？

1、量化子结构

原问题的最优解中涉及多少个子问题

在确定最优解使用哪些子问题时，需要考虑多少种选择

2、重叠子问题

三、最长公共子序列(LCS)

一个序列的子序列是在该序列中删去若干元素后得到的序列

最长公共子序列(LCS)问题：给定两个序列X和Y，求X和Y长度最大的公共子序列。

例如：X=“ABBCBDE” Y="DBBCDB" LCS(X,Y)="BBCD"

应用场景：字符串相似度比对

暴力穷举时间复杂度： 2^(m+n) ， m、n为两个序列的长度

LCS是否具有动态规划的最优子结构性质？

最后结果就是 c[m, n]

def lcs(x,y):
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]  #m+1 * n+1  初始化都是0
    b = [[0 for _ in range(n + 1)] for _ in range(m + 1)]  #记录方向箭头 1左上方 2上方 3左方
    for i in range(1, m+1):
        for j in range(1, n+1):
            if x[i-1] == y[j-1]:  #i j上的字符相等 匹配
                c[i][j] = c[i-1][j-1] + 1
                b[i][j] = 1
            elif c[i-1][j] > c[i][j-1]:  #i j上的字符不相等 不匹配 从上方来
                c[i][j] = c[i-1][j]
                b[i][j] = 2
            else:   #从左方来
                c[i][j] = c[i][j-1]
                b[i][j] = 3
    return c[m][n], b


def lcs_trackback(x, y):
    c, b = lcs(x, y)
    i = len(x)
    j = len(y)
    res = []   #存放最长公共子序列
    while i > 0 and j > 0:
        if b[i][j] == 1:  #来自左上方 说明该位置字符匹配
            res.append(x[i-1])
            i -= 1
            j -= 1
        elif b[i][j] == 2:  #来自上方
            i -= 1
        else:  #来自左方
            j -= 1
    return "".join(reversed(res))



x = "ABCBDAB"
y = "BDCABA"
c, b = lcs(x,y)
print(lcs_trackback(x, y))

<可能有多个最长公共子序列>

码农公寓