Dynamic programming

動機

寫個dp的總結，個人不喜歡課本上的什麼最佳子結構什麼的，所以不會有那種名詞只要懂遞迴就可以做dp了

對了，遞迴的函式預設有@cache，做記憶法

DP概述

Dynamic programming = planning over time

這裡的time要理解成順序，我們是在每個時間點上做決策，所以通常會需要資料有sort過或是本身有一定的順序

這些順序就是其他講解DP的資料會看提到的階段

DP 與 backtracking

Weighted interval scheduling: 每個job有weight挑job不重疊，並讓wieght最大

假設有job都已開始時間排序好，同時有一個函數(prev)可以給出前一個離最近的job

那就可以給出一個dp，就是看要不要這份job f(i)表示選到i時的最大wieght總和

@cache
def f(i):
  if i == 0:
    return jobs[i]
  else:
    return max(f(i-1), jobs[i]+f(prev[i]))

subset: 求subset 每一個都可以選或不選

def subset(arr):
  if not arr:
    return [[]]
  else:
    sub = subset(arr[1:])
    return sub+[s + [arr[0]] for s in sub]

可以看出dp與backtracking都是選與不選!! 那兩者差在哪裡?

backtrack需要之前的所有資料 dp可以利用有結合律函數(min, max, sum…)把之前的所有資料用一筆代表

不只一種DP

Weighted interval scheduling也可以這樣看

定義f(i,time)為在選第i樣工作，從time之前都有空

def f(i, time):
  if i == 0:
    return jobs[i]
  elif end[i] > time:
    return f(i-1)
  else:
    return max(f(i-1, time), jobs[i]+f(i-1, start[i]))

dp其實主要牽涉到怎麼設定狀態，像是把時間放進來，就會變成不同的dp 但前面利用前處理，讓找下一個job的速度上去，進而減少一個維度(參數)

DP 與 greedy

Greedy 不行就 DP

當 Greedy 不對就代表「這個問題不能只由這個子問題轉移」換句話說，Greedy 就是可以證明只有一個轉移來源的 DP

可以順便看列舉為什麼慢? 因為除了現在確定的參數外，還要繼續往後看才能確定答案

貪心就是只看當下，就ok了 DP是除了現在還要加上以前的資料

證明greedy

因為貪心就是只看當下，所以會需要證明這做法是對的

反證法：如果交換方案中任意兩個元素/相鄰的兩個元素後，答案不會變得更好，那麼可以推定目前的解已經是最優解了。
歸納法：先算得出邊界情況（例如）的最優解，然後再證明：對於每個，都可以由推導出結果。

常見題型

「我們將 XXX 按照某某順序排序，然後按某種順序（例如從小到大）選擇。」。
- 離線，先處理後選擇
「我們每次都取 XXX 中最大/小的東西，並更新 XXX。」
- （有時「XXX 中最大/小的東西」可以優化，比如用優先隊列維護）
- 在線，邊處理邊選擇解法
排序解法
- 用排序法常見的情況是輸入一個包含幾個（一般一到兩個）權值的數組，通過排序然後遍歷模擬計算的方法求出最優值。
後悔解法
- 思路是無論當前的選項是否最優都接受，然後進行比較，如果選擇之後不是最優了，則反悔，捨棄掉這個選項；否則，正式接受。如此往復。

DP 與 DAG

DP的狀態可以看成graph上的點

同時這個graph不會有環，所以是DAG

這樣DP其實就是求DAG的最長/短距離

recursion & iteration

iteration其實是recursion的特例

iteration，是直接從base case直接往上做，對應到bottom-up

recursion與iteration差在recursion要記憶當初誰call的context(用stack) 之後從頭往下，到底(base case)就照著stack往回走，這就是top-down

如果遞迴call的當下沒有其他要做的事，其實這個遞迴就是iteration

有context: sum(arr[1:])處理完還要與arr[0]的相加

def sum(arr):
  if not arr:
    return 0
  else:
    return arr[0]+sum(arr[1:])

沒context: sum(arr[1:],acc+arr[0])做完就沒有其他事了

def sum(arr,acc=0):
  if not arr:
    return acc
  else:
    return sum(arr[1:],acc+arr[0])

所以上面那個版本其實就是iteration，不過需要tail-recursion elimiation優化才有iteration的實際效能

top-down & bottom-up

top-down & bottom-up 不等價

Leetcode 718

如果用top-down，因為要追蹤每個range的長度，所以變成n^3 但是用bottom-up，長度自然是對的，所以變成n^2

Leetcode 546

只能用top-down去做，因為很難確定base case與怎麼從base case長上去反倒是top-down的分解，就很好做

技巧

狀態壓縮

其實就是把應該用set或array表示的狀態用bitmask表示

因為是bitmask，所以是整數，是整數就能dp

刷表法

省mem，locality變好

DP優化 (我不會，這個只會出現在競程)

太可怕了，就把資料列一列就好分治、DP 進階 Aliens 優化進階DP，DP優化

寫的小技巧

產生新值時固定寫法
- 有的是f[n + x] = combine(f[n], ....)
- 有的是f[n] = combine(f[n - x], ....)
- 最好固定寫法，個人是喜歡
  - f[n] = combine(f[n - x], ....)
  - 因為dp一定是由小的更新大的
bottom-up或是改寫時可以畫圖輔助
- 狀態怎麼到起點 (參數怎麼變化)
- 在table上是取什麼點 (方向)
從終點開始思考怎麼到起點 (top-down開始做)
- 除非bottom-up很明顯，或是top-down在這題是個悲劇

設計方式

dp就是由參數(遞迴的模型的組合)、對應的動作構成、定義回傳值，只能在求最佳化問題(有結合律的函數)使用

遞迴的模型

線性 (1D)
- f(i) = combine(f(j) for j in range(i))
區間 (2D)
- 列舉中點
  - f(i,j) = combine(combine2(f(i,k), f(k,j)) for k in range(i,j))
- 控制左右
  - f(i,j) = combine(f(i-1,j), f(i,j-1))
- 分塊
  - f(i,j) = combine(f(i,a), f(a,b), f(b,j)) for (a,b) in ...
點 (2D)
- 上、左、左上
  - f(i,j) = combine(f(i-1,j), f(i,j-1), f(i-1,j-1))
樹
- 子樹
  - f(root) = combine(f(child) for child in root.children)
set(狀態壓縮)
- f(state) = combine(f(next(state)))

上面是可能的遞迴方式，除了遞迴外，還有其他需要的訊息，像是座標、成本等等

需要遞迴的，加上其他需要的訊息，就是dp的狀態

動作

這就是看題目了，像是edit distance就有delete、replace、insert 動作會影響到

子問題怎麼組合
參數怎麼變化
有什麼參數

定義回傳值 (成本)

dp回來的值一定是可以與其他dp組合在一起的值，像

最大最小
總和
長度
…

通常我們會知道怎麼算最終答案的成本，但是dp時會需要計算當下狀態成本的方式，也就是需要把成本計算分散到每一層 這個吃狀態怎麼設計以及觀察範例可以看Optimal binary search trees的depth怎麼處理的

多看看其他人怎麼做

設計dp有的時候要自己加維度，就如同前面看到的dp不只一種，端看設計與實作

所以其實寫dp最重要的是觀察與想像，所以多做題

特別的DP

背包

01背包:

選到i，剩下space個空間

def f(i,space):
  if space < 0:
    return float('-inf')
  elif i < 0:
    return 0
  else:
    return max(f(i-1,space), price[i]+f(i-1, space-cost[i])) # !!

無限背包:

def f(i,space):
  if space < 0:
    return float('-inf')
  elif i < 0:
    return 0
  else:
    return max(f(i-1,space), price[i]+f(i, space-cost[i])) # !!

滾動 & 從頭或從尾

注意到i都是只有i-1，所以可以用滾動，但要改寫成bottom-up

01背包:

這裡與原本top-down的差不多，從i往前推

dp = [0] * W
for p,w in items:
  for nowW in reversed(range(w, W+1)):
    dp[nowW] = max(dp[nowW], p+dp[nowW-w])

無限背包:

這裡就與top-down完全不同了!!

top-down還是，從i往前推，但是可以在i停留，達成無限的效果 bottom-up為了要無限，所以必須每個合法的空間都要加一次，同時還要包含前面的影響

dp一定是小的先算好，所以一定從前面取，而現在我們想取的值是已經改變過的值，所以要從最小的空間開始往上推

01背包是不想取到已經改變過的值，所以要從最大的空間往下推

這裡也彰顯了從頭與從尾的不同!!

能不能拿到已經改變過的值?

從頭: 能
從尾: 不能

dp = [0] * W
for p,w in items:
  for nowW in range(w, W+1):
    dp[nowW] = max(dp[nowW], p+dp[nowW-w])

有環的DP

做離散化，每個點做一次
把環的長度變成兩倍

mutual recursion

Leetcode 188

最多賣k次，買完才能賣，求最大收益

sell[i][k] = 第i天，剩k次，做賣的最大收益
buy[i][k] = 第i天，剩k次，做買的最大收益

def sell(i,k):
  if k <= 0 or i < 0:
    return 0
  else:
    return max(sell(i-1,k), price[i]+buy(i-1,k-1))

def buy(i,k):
  if k <= 0 or i < 0:
    return float('-inf')
  else:
    return max(buy(i-1,k), -price[i]+sell(i-1,k-1))

為什麼要兩個? buy有自己的收益，sell也有自己的收益彼此又互相組成對方的收益

範例

來自演算法課本的dp範例

Algorithm Design(AD): 真的難，但有點東西 Introduction to Algorithm(CLRS): 厚到不能墊泡麵與當枕頭 Algorithms(DPV): 很薄，很精闢 The Algorithm Design Manual(TADM): 就是課本，但可以根據問題屬性去查對應的解法

edit distance

replace: (i-1,j-1)
delete: (i,j-1)
insert: (i-1,j)
- insert多一個字，又馬上比對，所以與delete相反

def f(s1,s2):
  if not s1 and not s2:
    return 0
  elif s1[0] == s2[0]:
    return f(s1[1:], s2[1:])
  else:
    return 1+min(f(s1[1:], s2[1:]), f(s1, s2[1:]), f(s1[1:], s2))

Longest common subsequence & Longest increasing subsequence

Longest Increasing Subsequence

Maximum Subarray Sum (AD)

Maximum Subarray Sum

Traveling Salesman Problem

給定一系列城市和每對城市之間的距離，求訪問每一座城市一次並回到起始城市的最短迴路

cities是還可以去的點，1011，還有2, 1, 0可以去 i是目前的位置

def f(cities, i):
  if cities == 0:
    return 0
  else:
    return min([f(cities ^ (1 << i), j) + weight[i][j] for j in edges[i] if (1 << j) & cities) != 0], float('inf'))

Hamiltonian Path

有沒有一條每一點剛好經過一次的路線，起點和終點可以不相同

N是有幾個地點(len(graph.V()))

remains是還可以去的點，1011，還有2, 1, 0可以去 i是目前的位置

def f(remains, i):
  if remains == 0:
    return True
  else:
    return any(f(remains ^ (1 << i), j) for j in edges[i] if (1 << j) & remains) != 0)

Shortest paths (DPV)

path本身就是一段接一段的，也就是說它本身就是遞迴

可以回去，所謂的relaxtion，其實就是在原有的基礎上衍伸一段可以到的edge 這就是list!!

如果求最短，就是min，是具有結合律的函數，可以dp

所以可以列舉起、終點、中間點，一直更新最短長度

Rod cutting (CLRS)

給一條木頭，與長度對應到的價格，求最大收益

def f(size):
  if size == 0:
    return 0
  else:
    return max(f(size-sub)+price for sub,price in size2price.items() if size-sub >= 0)

Matrix-chain multiplication (CLRS, DPV)

有一排matrix要乘，求計算成本最小

成本: (a X b) * (b X c) = (a X c) 的成本是 b

def f(i,j):
  if j-i <= 1: # 不會有一個matrix相乘
    return float('inf')
  else:
    return min(f(i,k)+f(k+1,j)+cost(k,k+1) for k in range(i+1, j-1))

Optimal binary search trees (CLRS)

給key與出現的頻率，組成一個搜尋成本最小的BST

成本: sum(freq[i]*depth)

一個是tree，所以要分左右一個是範圍，所以有i,j

再來是計算成本，所以先把depth傳進去

def f(i,j,dep):
  if j-i == 0:
    return 0
  else:
    return min(f(i,k,dep+1)+f(k+1,j,dep+1)+freq[key[k]] * dep for k in range(i,j-1))

有沒有辦法把depth消滅掉? 看成橫的先看tree

      i
   i-1 i+1
i-2        i+2

再看當時遞迴的範圍

              [i-2~i+2]
     [i-2~i-1]         [i+1~i+2]
[i-2]                           [i+2]

以i+2來說，由上往下看被加了3次，只看遞迴時的範圍，會發現剛好都i+2出現了3次所以可以把depth去掉，變成每一次就把整個遞迴範圍的freq加總就好

def f(i,j):
  if j-i == 0:
    return 0
  else:
    return min(f(i,k)+f(k+1,j)+sum(freq[i:j]) for k in range(i,j-1))

Minimum Length Triangulation (TADM)

有一堆點，構成一個多邊形，把多邊形切成三角形，讓成本最小

成本: 所有三角形邊長的總和

def dist(p1, p2):
    return sqrt((p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]))
 
def cost(points, i, j, k):
    return dist(points[i], points[j]) + dist(points[j], points[k]) + dist(points[k], points[i])

def f(i,j):
  if j-i <= 2:
    return float('inf')
  elif j-i == 3:
    return cost(i,i+1,j)
  else:
    return min(f(i,k) + cost(i,k,j) + f(k,j) for k in range(i,j))

Independent sets in trees (DPV)

Independent set就是裡面的點沒有edge互連，求最多點的set

就是選了root就不能選children，但可以加上grand-children

f(root) = max(sum(f(children)), 1+sum(grand-children))

Maximum Rectangle Problem (AD)

給個matrix，求從中框出的長方形的內部數字總和

先做row的prefix sum 再根據前面的prefix sum，做每個column的prefix sum

之後就是用排容: f(i,j,n,m) = area(i,j) - area(i-n,j) - area(i,j-m) + area(i-n, j-m)

Segmented least squares (AD)

有一堆點，要用最少的線去fit這些點

定義回傳值: cost

定義cost: 每個點的e + 常數*幾根線

用到Optimal binary search trees把depth分散到每一層去做的技巧

def error(i,j):
  # Check 6. DYNAMIC PROGRAMMING I page 30
  pass

def f(i):
  if i == 0:
    return 0
  else:
    return min(error(k,i) + 常數 + f(k-1) for k in range(i))

Find the longest path in a matrix with given constraints

這裡要注意的是沒有去重的東西，所以開始dfs時要從終點開始走

def path(i,j):
    ret = float('-inf')
    if 0 <= i < n and 0 <= j < m:
        if (i,j) == (n-1,m-1):
            ret = 0
        else:
            dirs = [(i-1,j),(i,j-1),(i+1,j),(i,j+1)]
            ret = max(ret, *[path(x,y) for (x,y) in dirs])
    return ret

for i in reversed(range(n)):
    for j in reversed(range(m)):
        path(i,j)

Assembly Line Scheduling

dag最長路徑

# t :: time to switch another line
# a :: time of each station
# e :: cost on starting line
# x :: cost on goal
def f(i,j):
    if j == 0:
        return e[i] + a[i][j]
    ret = min(f(i,j-1), t[int(not i)][j-1]+f(int(not i), j-1))
    if j == len(t[0]): # at goal
        ret += x[i]
    return ret

Optimal Strategy for a Game

一開始先用一個me表示對面在做決策有點像買股票的那一提

def f(i,j,me):
    if i>j:
        return 0
    elif i==j:
        return arr[i] if me else 0
    else:
        if me:
            # ????
            return max(arr[i]+f(i+1,j,not me), arr[j]+f(i,j-1,not me))
        else:
            # ????

Q: 看別人的分數幹嘛 A: 雖然說我們的結果與他們有關，但是他的分數與我們無關

下面的也是類似的

def x(i,j):
    if i>j:
        return 0
    elif i == j:
        return arr[i]
    else:
        return max(arr[i]-y(i+1,j), arr[j]-y(i,j-1))
def y(i,j):
    if i>j:
        return 0
    elif i == j:
        return arr[i]
    else:
        return max(arr[i]-x(i+1,j), arr[j]-x(i,j-1))

選下一輪能選的時候分數最少的case (關注要建構的目標)

def f(i,j):
    if i>j:
        return 0
    elif i == j:
        return arr[i]
    else:
        return max(arr[i]+min(f(i+2, j), f(i+1,j-1)), arr[j]+min(f(i,j-2), f(i+1,j-1)))

Partition problem

def f(i,cnt):
    if i == 0:
        return arr[i] == cnt
    else:
        return f(i-1,cnt-arr[i]) or f(i-1,cnt)
return f(len(arr)-1, sum(arr)//2) if sum(arr) % 2 == 0 else False

Partition a set into two subsets such that the difference of subset sums is minimum

這個會變成backtrack

def f(i, cnt):
    if i == 0:
        return abs((sum(arr) - cnt) - cnt)
    else:
        return min(f(i - 1, cnt+arr[i - 1]), f(i - 1, cnt))

原因是f想直接算差值，但是差值一定要等到最後，把所有路都走過可以對其中一個維度做離散化

def f(i, cnt):
    if i == 0:
        return cnt == 0
    else:
        return f(i-1, cnt) or f(i-1,cnt-arr[i])

for n in reversed(range(sum(arr)//2)):
    if f(len(arr)-1, n):
        print(sum(arr)-2*n)

題外話: functional DP

函数式的动态规划

Ref

Greedy & DQ & DP 夜深人静写算法（二）- 动态规划入门 6. DYNAMIC PROGRAMMING I 背包 DP

動機#

DP概述#

DP 與 backtracking#

不只一種DP#

DP 與 greedy#

證明greedy#

DP 與 DAG#

recursion & iteration#

top-down & bottom-up#

top-down & bottom-up 不等價#

Leetcode 718#

Leetcode 546#

技巧#

狀態壓縮#

刷表法#

DP優化 (我不會，這個只會出現在競程)#

寫的小技巧#

設計方式#

遞迴的模型#

動作#

定義回傳值 (成本)#

多看看其他人怎麼做#

特別的DP#

背包#

滾動 & 從頭或從尾#

有環的DP#

mutual recursion#

範例#

edit distance#

Longest common subsequence & Longest increasing subsequence#

Maximum Subarray Sum (AD)#

Traveling Salesman Problem#

Hamiltonian Path#

Shortest paths (DPV)#

Rod cutting (CLRS)#

Matrix-chain multiplication (CLRS, DPV)#

Optimal binary search trees (CLRS)#

Minimum Length Triangulation (TADM)#

Independent sets in trees (DPV)#

Maximum Rectangle Problem (AD)#

Segmented least squares (AD)#

Find the longest path in a matrix with given constraints#

Assembly Line Scheduling#

Optimal Strategy for a Game#

Partition problem#

Partition a set into two subsets such that the difference of subset sums is minimum#

題外話: functional DP#

Ref#

動機