algorithm, dynamic programming, dp,

算法笔记101 - 动态规划 Dynamic Programming

DolorHunter DolorHunter Follow Oct 17, 2021 · 16 mins read

算法笔记101 - 动态规划 Dynamic Programming
Share this

动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

递归代码简洁又可读,但是因为会可能重复计算子问题,所以往往不能直接写递归。我们需要有一块空间用来存储已经计算过的数据,这样再次使用时只需要取用,就避免了重复运算。当然动态规划也不只能用在对递归的优化上,很多具有状态转移的 Brute Force 办法也能用DP进行优化。

动态规划被用来求最优解,难点主要就是找递归关系(状态转移方程)。

动态规划

动态规划应用于子问题重叠的情况:

  1. 问题有递归解法(状态转移)
  2. 开辟存储空间;
  3. 找到计算子问题的顺序

比如说动态规划的常用例子,Climbing Stairs(上楼梯问题),Wood Cutting (木条/钢条切割) ,Knapsack (背包问题)等等就是如此实现的。

Climbing Stairs (爬楼梯问题)

爬楼梯问题其实就是斐波那契数列(Fibonacci sequence),只不过用每次可以上一级或两级楼梯来包装了一下。状态转移方程都是 $T(n) = T(n-1) + T(n-2)$,即第 n 次的可能性为 n-1 次的可能性与 n-2 次的可能性之和。

斐波那契数列常用递归计算,但是因为递归会重复计算内容,例如下面的 fib(5) 将 fib(3) 计算了 2 次,fib(2) 计算了 3 次,fib(1) 计算了 4 次,fib(0) 计算了 2 次。时间复杂度为O($2^n$)。

def fib(n):
    if n <= 1:
        return n
    return fib(n  1) + fib(n  2)

fib 5

sourse: Wikipedia - Fibonacci Tree 5.svg

因此我们在找到 Base Case (n=0为0, n=1为1) 和状态转移方程 $T(n) = T(n-1) + T(n-2)$ 后,可以用 DP 来实现这个问题的解。开辟一块存储空间,之后从小到大逆序计算 fib。计算后的 fib 存入存储空间中,需要用时从存储中取值即可。时间复杂度为 $O(n)$,空间复杂度为 $O(n)$。

# big o = n
def fib(n):
    mem = [0 for _ in range(n+1)]
    for i in range(n+1):
        if i <= 1:
            mem[i] = i
        else:
            mem[i] = mem[i-1] + mem[i-2]
    return mem[n]


ans = fib(5)
print(ans)
# 5

Wood Cutting (木条/钢条切割)

木条切割问题给定一段钢条,和不同长度的价格,问如何切割使得总价格最大。通过找到状态转移方程 best 计算最大总价格,并且把最大价值选择的切口记录到 choice 中。

$best[i]=max^{i}_{j=1}\left { best[j]+min(best[i]+price[i-j]) \right }$

$choice[i] = choice[j-1]+[i-j+1]$

初始化 best 和 choice,并且通过两层遍历找到最优解,存入 best[i] 与 choice[i]。当遍历完成后,结果在 best[n] 与 choice[n] 中。时间复杂度为 $O(n^2)$,空间复杂度为 $O(n^2)$。

# big o = n^2
def wood_cutting(price):
    n = len(price)
    best, choice = [0 for _ in range(n+1)], [[] for _ in range(n+1)]
    for i in range(1, n+1):
        temp_max = 0
        temp_choice = []
        for j in range(1, i+1):
            temp = best[j-1] + price[i-j]
            if temp > temp_max:
                temp_max = temp
                temp_choice = choice[j-1] + [i-j+1]
        best[i] = temp_max
        choice[i] = temp_choice
    return best[n], choice[n]


ans = wood_cutting([1,18,24,36,50,50])
print(ans)
(54, [2, 4])

射击问题

射击问题类似钢条切割问题。陨石与时间关系为 x,蓄力时间与攻击关系为 d,要求如何射击使得击落陨石最多。

例如 (x1, x2, x3, x4) = (1, 10, 10, 1), (d1, d2, d3, d4) = (1, 2, 4, 8)。最佳解法为 5(在 3 和 4 的时候射击)。

# big o = n^2
def best_laser_dp(x, d):
    xn, dn = len(x), len(d)
    best, choice = [0 for _ in range(xn+1)], [[] for _ in range(xn+1)]
    for i in range(1, xn+1):
        temp_max, temp_choice = 0, []
        for j in range(1, i+1):
            temp = best[j-1] + min(x[i-1], d[i-j])
            if temp > temp_max:
                temp_max = temp
                temp_choice = choice[j-1] + [i]
            best[i] = temp_max
            choice[i] = temp_choice
    return best[xn], choice[xn]


ans = best_laser_dp([1, 10, 10, 1], [1, 2, 4, 8])
print(ans)
# (5, [3, 4])

Knapsack 0/1 (0/1背包问题)

已知一些物品 (k) 的重量 ($w_k$)、价值 ($v_k$),以及背包的总容量 (w),求背包可以装载的最大价值。

背包问题为二维DP问题,比前面的爬楼梯、钢条切割与射击问题要难一些。背包问题的 Base Case 为 k=0 或 w=0 时, best[k, w]=0,即没有物品用于装载或者是背包没有装载空间时,价值为 0。

背包装载分为三种情况:

  1. 没有空位装载物品 best[k, w] = best[k-1, w]
  2. 有空位并且装载物品 best[k, w] = best[k, w-wk] + vk
  3. 有空位但是不装载物品 best[k, w] = best[k-1, w]
# big o = n^2
def knapsake(val, weight, max_weight):
    k, w = len(val), max_weight
    best = [[0 for _ in range(w + 1)] for _ in range(k + 1)]
    for i in range(k + 1):
        for j in range(w + 1):
            if i == 0 or j == 0:
                best[i][j] = 0  # base case
            elif j - weight[i-1] < 0:
                best[i][j] = best[i-1][j]  # case 1
            else:
                val_with_kth = best[i-1][j-weight[i-1]] + val[i-1]  # case 2
                val_without_kth = best[i-1][j]  # case 3
                best[i][j] = max(val_with_kth, val_without_kth)
    return best[k][w]


ans = knapsake([3,5,6], [1,2,3], 4)
print(ans)
# 9

Matrix Chain Multiplication (矩阵串乘法)

不同位置矩阵相乘的结果不同,目标将矩阵串相乘,并且找到结果最小的乘法结果。

如果使用 Brute Force 解法,复杂度约为 $Ω(4^n/n^{(3/2)})$。但使用 DP 复杂度为 $O(n^3)$。代码参考 mskitten - dp方法论——由矩阵相乘问题学习dp解题思路

# big o = n^3
def mat_chain_mul(chain):
    n = len(chain)
    best = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n-1, -1, -1):
        for j in range(i+1, n):
            if i == j:
                best[i][j] = 0
            else:
                temp_min = 65535
                for k in range(i, j):
                    ri, ck, cj = chain[i][0], chain[k][1], chain[j][1]
                    temp = best[i][k] + best[k+1][j] + ri*ck*cj
                    if temp < temp_min:
                        temp_min = temp
                best[i][j] = temp_min
    return best[0][n-1]


ans = mat_chain_mul([[30, 35], [35, 15], [15, 5], [5, 10], [10, 20], [20, 25]])
print(ans)
# 15125

Perfect Squares(长方形分割为正方形问题)

将 n*m 的长方形切分为若干个正方形 (Perfect Squre),求最小需要切几次。遍历行列,并且用 a 作为分割线计算最小切割数量,时间复杂度 O($n^3$)。思路参考 CSDN - 动态规划处理长方形分割为正方形问题

# big o = n^3
def chocolate(n, m):
    cut = [[0 for _ in range(m+1)] for _ in range(n+1)]
    for i in range(n+1):
        for j in range(m+1):
            # perfect square
            if i == j:
                cut[i][j] = 1
            # cut[i][j] = min(cut[i-a][j] + cut[a][j]
            #                 cut[i][a] + cut[i][j-a])
            else:
                temp_min = 65535
                for a in range(1, i):
                    temp = cut[i-a][j] + cut[a][j]
                    if temp < temp_min:
                        temp_min = temp
                for a in range(1, j):
                    temp = cut[i][a] + cut[i][j-a]
                    if temp < temp_min:
                        temp_min = temp
                cut[i][j] = temp_min
    return cut[n][m]


ans = chocolate(5, 6)
print(ans)
# 5

Highway Billboard (公路广告牌)

广告牌问题要求在 D 间隔外安装广告牌,要求整体收益最大。有点类似 0/1 背包问题,但是选项更为简单,只需要找到距离为 D 以上的广告牌 (best buddy),比较当前广告牌和 best buddy 收益和与前一个广告牌的收益和,取两值的最大效益即可。难点在于需要预先计算 best buddy,就能把复杂度从 $n^2$ 降低至 $n$。数据参考 includehelp - Highway billboard

# big o = n
def highway_billboard(x, val, dist):
    n = len(x)
    r, l = n-1, n-1
    # pre-process best buddy
    best_buddy = [0 for _ in range(n)]
    best = [0 for _ in range(n)]
    while r > 0 and l > 0:
        if x[r] - x[l] >= dist:
            best_buddy[r] = l
            r -= 1
            l = r
        else:
            l -= 1
    for i in range(1, n):
        best[i] = max(best[i-1], val[i] + best[best_buddy[i]])
    return best[n-1]


ans = highway_billboard([6,7,12,13,14], [5,6,5,3,1], 5)
print(ans)
# 11

Longest Common Sub-sequence (最长公有子序列)

已知两个字符串,求最长公有子序列。公有序列并不需要连续,例如 abcb 和 bdcabd 的最长公有序列为 bcb。

最长公有序列分为两种情况:

  1. 元素相等 x[i]==y[j],LCS[i][j] = LCS[i-1][j-1] + 1
  2. 元素不等 x[i]!=y[j],比较 x[i-1]==y[j],x[i]==y[j-1],LCS[i][j] 取长的序列
# big o = n^2
def longest_common_subsequence(x, y):
    xn, yn = len(x), len(y)
    lcs = [[0 for _ in range(yn+1)] for _ in range(xn+1)]
    for i in range(xn+1):
        for j in range(yn+1):
            if i == 0 or j == 0:  # base case
                lcs[i][j] = 0
            elif x[i-1] == y[j-1]:  # eq
                lcs[i][j] = lcs[i-1][j-1] + 1
            else:  # not eq
                lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])
    return lcs[xn][yn]


ans = longest_common_subsequence('abcb', 'bdcab')
print(ans)
# 3

Typesetting (整齐打印)

调整每行单词的数量,使得每行行末的空格方差最小。题目参考 huihoo - Application: Typesetting Problem

# big o = n^2
def typesetting(words, m):
    n = len(words)
    best, choice = [0 for _ in range(n+1)], [[] for _ in range(n+1)]
    s = [[0 for _ in range(n+1)] for _ in range(n+1)]
    for i in range(1, n+1):
        s[i][i] = m - words[i-1]
        for j in range(i+1, n+1):
            s[i][j] = s[i][j-1] - words[j-1] - 1
            if s[i][j] < 0:
                while j <= n:
                    s[i][j] = 65535
                    j += 1
                break
    for i in range(1, n+1):
        temp_min = 65535
        temp_choice = []
        for j in range(i):
            temp = best[j] + s[j+1][i] ** 2
            if temp < temp_min:
                temp_min = temp
                temp_choice = choice[j-1] + [j]
        best[i] = temp_min
        choice[i] = temp_choice
    return best[n], choice[n]


ans = typesetting([2,3,3,4,2,6,2,3,3,5,2,6,2,3,3,3,2,7,2,3,3,3,2,12,2,3,3,5,2,7,2,3,3,5,2,12,2,3,3,6,2], 42)
print(ans)
# (123, [0, 7, 15, 24, 34])

总结

DP 问题大概的流程可以分为三步:Base Case -> 状态转移关系 -> 分支条件。

DP 问题的模板包括:开辟 best 空间(n+1),按顺序循环计算 best,返回 best[n](通常为末元素)。

def dp(arr):
    n = len(arr, val)
    # 通常 0 为 base case 存放位置,计算 1~n
    best = [0 for _ in range(n+1)] 
    for i in range(n+1):
        # 第0行/列通常存放 Base Case
        if i == 0:
            best[i] = 0
        # 分支条件1
        elif i < best[i-1]:
            # 状态转移方程1
            best[i] = min(best[i-1], best[i-2] + val[i])
        # 分支条件2
        else: 
            # 状态转移方程2
            best[i] = max(best[i-3], best[i-4]  + val[i])
    return best[n]

不同的 DP 问题区别通常在于 best 的规模(一维或二维,或者多个 best),循环方向,分支条件,最佳化条件 (max/min)。DP 的难点主要是在抽象出状态转移方程,以及描述各个参数的关系和范围。

参考资料:

Join Newsletter
Get the latest news right in your inbox. We never spam!
DolorHunter
Written by DolorHunter
Developer & Independenet Blogger