動態規劃

星期六的訓練將談及動態規劃（Dynamic Programming, DP），
因為要預備講義的關係，
所以今日比較懶，
用講議來當今天的日記。

所謂動態規劃，
並不是一種算法，
而是一種解決問題的技巧。
它可以明顯地降低一些算法（當然不是全部）的執行時間，
而代價就是使用多些記憶體。

動態規劃其實是以「空間換取時間」，
藉著記下曾運算的結果，
減少重覆運算的次數，
從而增加程式的效率。

一般來說，
要使用 DP，
要符合兩個條件。
1. Optimal sub-structure：
子問題的最佳答案一定是組成原問題最佳答案的原素。
2. Overlapping sub-problems
要有重複計算的子問題。

這兩個條件，
前者確保 DP 找出來的答案的真確性，
後者確保了有用 DP 的需要。

常見的 DP 題目包括：
1.矩陣乘法（Matrix Chain Multiplication, MCM）
2.最長公共子字串（Longest Common Subsequence, LCS）
3.編輯距離（Edit Distance）
4.最長遞增/減子數列（Longest Inc/Dec-reasing Subsequence, LIS/LDS）


矩陣乘法（Matrix Chain Multiplication, MCM）

跟據矩陣的乘法結合律（Associativity of Multiplication），
三個距陣 A(10*100)、B(100*5) 和 C(5*50)，
A(BC) = (AB)C
先算那個乘法，
雖然不影響答案，
卻會影響效率。

前者做的乘數運算為 100 * 5 * 50 + 10 * 100 * 50 = 75000 次，
後者做的乘數運算為 10 * 100 * 5 + 10 * 5 * 50 = 7500次。
可見後者比前者少 10 陪的運算。

現在給你一串的矩陣，
採取那種組合次取可做最少的乘數運算？

假設有 n 個矩陣，
A[i, j] (i <= j) 代表把第 i 個矩陣至第 j 個矩陣相乘後的矩陣。
A[i, j] 可以由 A[i, k] 和 A[k+1, j] (i <= k < j) 相乘而得到，
總共有 j-i 種分拆法。 (k = i, i + 1, ..., j - 1)

假設 R[i] 代表距陣 i 有多少行，
C[j] 代表距陣 i 有多少列，
A[i, k] 和 A[k+1, j] 相乘所需的乘數運算將會是：
R[i] * C[k] * C[j]。

設 O[i, j] 為組成 A[i, j] 所需的最少乘數運算，
O[1, n] 將會是我們要找的答案。

問題是：
如何找出 O[1, n]？

因為 A[i, j] 由 A[i, k] 和 A[k+1, j] 相乘得來，
所以

O[i, j] = 0, if i = j
        = min {O[i, k] + O[k+1, j] + R[i] * C[k] * C[j]} i <= k < j, if i < j

練習：
348 Optimal Array Multiplication Sequence


最長公共子字串（Longest Common Subsequence, LCS）

假設有兩個字串，
A G C T A T A C G A T G A C T
G T C A G T A T A G T C A T A T G
這兩個字串的最長公共部份是：
G C T A T A G A T A T

我們試試這樣排

A G   C     T A T A C G     A T G A C T
  G T C A G T A T A   G T C A T   A   T G

假設輸入的兩個字串為 X 和 Y。
檢查 X 和 Y 兩個字串的第一個字符，
有兩個可能性：
1. 若他們相同，
那最長公共部份必包含此字符，
由字串去取最頭的字符得 X' 和 Y'，
X 和 Y 的最長公共部份長度會是 X' 和 Y' 的最長公共部份長度 + 1；

2. 若不相同，
X 和 Y' 的最長公共部份長度，
或是 X' 和 Y 的最長公共部份長度將會是我們要找的答案。

練習：
10066 The Twin Towers


編輯距離（Edit Distance）

假設有有兩個字串 X 和 Y，
透過刪減字符、增加字符和/或轉換字符，
將 X 變成 Y。

假設 d(X, Y) 為字串 X 和 Y 的最短距離，
我們可得：

d("", "") = 0
d("", s) = d(s, "") = 字串 s 的長度
d(s1 + c1, s2 + c2)
= min{ d(s1, s2) + if (c1 == c2) then 0 else 1,
       d(s1 + c1, s2) + 1,
       d(s1, s2+c2) + 1
     }

首兩條式很明顯，
比較難理解的可能是最尾那條。
在最尾那條式，
兩個字串均不是空字串，
考慮這兩字串最尾的字符 c1 和 c2。
如 c1 = c2，
不需要做任何變化，
所以最短距離 = d(s1, s2)；
如他們不相同，
可以轉換 c1 變成 c2，
最短距離 = d(s1, s2) + 1；
或可以刪除 c1，
最短距離 = d(s1, s2 + c2) + 1；
增加 c2 在第一個字串的尾，
最短距離 = d(s1 + c1, s2) + 1；


練習：
164 String Computer


最長遞增/減子數列（Longest Inc/Dec-reasing Subsequence, LIS/LDS）

在一串數列中，
尋找一條最長上升/下降數列。

設 L[i] 為至數列第 i 個數為止，
最長上升/下降數列長度。
V[i] 為數列第 i 個數的值。
L[i] = max{1, L[j] + 1 if V[i] >/< V[j]}, 1 <= j < i

練習：
10131 Is Bigger Smarter

另外有一個較有效的算法（O(n log k)）。
參考資料
設有一個已排列的陣列 A
A[i] 代表如果有一長度為 i 的 遞增/減子數列時，
最後一個（即係第 i 個）的值。
每輸入一個數，
就用 binary search 尋找他的最後位置是甚麼。

Pseudocode：

A[0] := -1
A[1] := Inf
K := 0
While there are elements left
      Read in the next element X
      Find L such that A[L] <= X < A[L+1]
      A[L+1] := X
      If L+1 > K
         K := K + 1
         A[K+1] := Inf
Output K

練習：
481 What Goes Up