# Algorithm Chapter 15 - Dynamic Programming

## Introduction

* 動態規劃 (Dynamic Programming) 並非某種特定的演算法，而是一種策略（就像 divide-and-conquer 之類的）
* "programming" 一詞，在這個策略被發明出來的年代還是指「查表法」的意思，並非現在的程式設計
* 是專門用來解決最佳化問題的策略（找最大值或最小值）
* 基本上會分成四個步驟
* 分析問題的本質，確認是否有**重疊子問題**，以及這些子問題是不是**最佳子結構 (Optimal substructure)**
* 將最佳解寫成最佳子結構的解的**遞迴式**
* 用 **bottom-up** 的方式，計算子結構們的最佳解，並將**結果儲存在表中**
* 用計算得出的結果找出整個問題的最佳解
* 最佳子結構 (Optimal Substructure)， 指的是局部最佳解能決定全局最佳，換句話說，即問題能夠被分解成子問題來解決

## Rod Cutting Problem

* `int rod_cutting(int n, int price_table[])`
* 給定一個長度為 $n$ 的鐵條，以及不同的鐵條長度所對應到的金額表，試問如何分割鐵條才能得到最大的利益？
* input: 鐵條的長度 $n$ （整數），以及不同長度對應的金額表（一維整數陣列）
* output: 金額的最大值（和得到此最大值的分割方法）

### Brute-force algorithm

* 列出所有可能的切繩子的組合，分別計算每一種組合的價格，再挑出最大者
* 因為每一個段落長度都必須是整數，所以總共會有 $2^{n - 1}$ 種切法（長度 $n$ 共有 $n - 1$ 個切點，每個點可切可不切有 2 種選擇，所以是 $2^{n - 1}$ 種）
* 求解每一個子問題需要 $O(n)$ 的時間，所以暴力解的時間複雜度為 $O(n \times 2^n)$

### Simple Recurrence

* 不管是哪一種切法，其金額都是由更短的段落的金額所組合出來的。如果一次只切一刀，則長度 $n$ 的繩子最佳價值，記為$r_n$，可能是
* $p_n$: 長度為 $n$ 的價值
* $r_1 + r_{n - 1}$: 長度為 1 的價值加上長度為 $n - 1$ 的價值
* $r_2 + r_{n-2}$: 長度為 2 的價值加上長度為 $n - 2$ 的價值
* ......
* $r_{n - 1} + r_1$: 長度為 $n - 1$的價值加上長度為 1 的價值
* 亦即 $r_n = \max(p_n,\ r_1 + r_{n - 1},\ r_2 + r_{n - 2},\ ...,\ r_{n - 1} + r_1)$
* 如此定義會將 $r_n$ 分解成兩個子問題，但其實可以將問題更簡化，以「第一刀切在 $i$ 位置」的方式，遞迴分割整條繩子，此時$r_n = \max \limits_{1 \leq i \leq n}(p_i + r_{n - i})$， 當中的 $p_i$ 可以透過查表求得，子問題變成只有一個
* 根據這條式子，以 top-down 的方式下去求解，可以使用以下的程式

    function cut_rod(p, n){
        if(n === 0){
            return 0;
        }
        let q = -inf;
        for(let i = 1; i <= n; ++i) {
            q = Math.max(q, p[i] + cut_rod(p, n - i));
        }
        return q;
    }

* 雖然比暴力解好一點，但還是慢的不可思議，時間複雜度高達 $O(2^n)$
* 因為這個遞迴方式沒辦法避免重複計算相同的子問題，所以浪費了很多時間

### Dynamic Programming

* 由上方定義可知，總長為 $n$ 的最佳值是透過更短長度的最佳值湊出來的，也就是說，如果要得到完整問題的最佳解，只要求出子問題的最佳解並進行加總即可。這種可以透過求得子問題的最佳解而得到全局問題的最佳解的結構稱為**最佳子結構**
* 另一方面，切繩問題有很多的**重複子問題**，亦即相同的片段長度最佳解可能會被重複計算多次。為了避免重複的計算浪費時間，我們可以把已經算過的答案存在一個表裡頭，當第二次遇到同樣的問題時就去查表，就可以免去再一次計算所花的時間
* 雖然會費去較多的儲存空間，但是 DP 往往可以把指數時間複雜度的問題降為多項式時間，以少量的空間換取大量的時間可以說是非常划算
* 以切繩問題來說， DP 可以有 top-down 的解法和 bottom-up 的解法（通常大部分的問題會是用 bottom-up 的解法較多）
* DP top-down 版本

    function cut_rod_top_down(p, n) {
        let r = [];
        for(let i = 0; i <= n; ++i) {
            r.push(-inf);
        }
        return cut_rod(p, n, r);
    }

    function cut_rod(p, n, r) {
        let q;
        if(r[n] >= 0) return r[n];
        if(n === 0) {
            q = 0;
        }
        else {
            q = -inf;
            for(let i = 1; i <= n; ++i) {
                q = Math.max(q, p[i] + cut_rod(p, n-i, r));
            }
            r[n] = q;
        }
        return q;
    }

* DP bottom-up 版本（少很多層 stack， 理論上更快）：

    function cut_rod_bottom_up(p, n) {
        let r = new Array(n + 1);
        r[0] = 0;
        for(let j = 1; j <= n; ++j) {
            let q = -inf;
            for(let i = 1; i <= j; ++i) {
                q = Math.max(q, p[i] + r[j - i]);
                r[j] = q;
            }
        }
        return r[n];
    }

* 無論是哪一種，使用 DP 求解均可在 $\Theta(n^2)$ 時間內解決問題
* top-down: 使用均攤法分析，詳見詳見 17 章
* bottom-up: 雙層 for 迴圈，每圈最多跑 n 次
* 除了求得最佳解的值之外，DP 還可以求得最佳解的切法
* 把得到最佳值的那個解切下的那刀的位置儲存在另一個 table 當中，就可以用另一個 function 來印出答案
* 最佳解可能不只一種，但是最佳值肯定是只有一種的， DP 只要可以印出其中一種切法即可

        let r = new Array(n + 1); // for optimal value
        let s = new Array(n + 1); // for optimal solution

        function cut_rod_with_solution(p, n) {
            r[0] = 0;
            for(let j = 1; j <= n; ++j) {
                let q = -inf;
                for(let i = 1; i <= j; ++i) {
                    if(q < p [i] + r [j – i]) {
                        q = p[i] + r[j - i];
                        r[j] = q;
                        s[j] = i;
                    }
                }
            }
            return r[n];
        }

        function cut_rod_print_solution(p, n) {
            while(n > 0) {
                console.log(s[n]);
                n -= s[n];
            }
        }

## Longest Common Subsequence

* `array LCS(array X[], array Y[])`
* 給定兩個序列 $X = \langle x_1, ..., x_m \rangle$ 及 $Y = \langle y_1, ..., y_n \rangle$， 求這兩個序列所共同擁有的最長的子序列
* 注意：子序列不一定要是連續的，只要前後的相對位置正確即可
* input: 兩個陣列，通常是字串或是陣列
* output: 最長的共同子序列

### Brute-force algorithm

* 窮舉 $X$ 的所有子序列，每一個都去檢查他是不是 $Y$ 的子序列
* $X$ 長度為 $m$， 從空字串到 $X$ 本身總共有 $2^m$ 個子序列
* $Y$ 的長度為 $n$， 要檢查是不是 $Y$ 的子序列約需要 $n$ 次比較
* 時間複雜度為 $\Theta(n \times 2^m)$

### Dynamic Programming

* 找出最佳子結構
* 定義序列 $X$ 的前綴 (prefix) $X_i = \langle x_1, ..., x_i \rangle$
* 令 $Z = \langle z_1, ..., z_k \rangle$ 為$X$ 和 $Y$ 的任意最長共同子序列，有以下定理
* 若 $x_m = y_n$ 且 $z_k = x_m = y_n$， 則 $Z_{k - 1}$ 亦為 $X_{m - 1}$ 和 $Y_{n - 1}$ 的最長共同子序列
* 若 $x_m \neq y_n$ 且 $z_k \neq x_m$， 則 $Z$ 為 $X_{m - 1}$ 和 $Y$ 的最長共同子序列
* 若 $x_m \neq y_n$ 且 $z_k \neq y_n$， 則 $Z$ 為 $X$ 和 $Y_{n - 1}$ 的最長共同子序列
* 證明：
- 首先，若 $Z$ 為 $X$ 及 $Y$ 的最長共同子序列，則 $z_{k} = x_{m} = y_{n}$ 。若不是，則存在另一個子序列 $Z' = \langle z_{1}, ..., z_{k}, x_{m} \rangle$ ，此序列亦為 $X$ 及 $Y$ 的共同子序列，且長度比 $Z$ 更長，與 $Z$ 為最長共同子序列的假設互相矛盾。所以 $z_{k} = x_{m} = y_{n}$ 必成立
- 再來，若 $z_{k} = x_{m} = y_{n}$ ，則 $Z_{k-1}$ 亦為 $X_{m-1}$ 和 $Y_{n-1}$ 的最長共同子序列。若不是，則存在一個序列 $W$ 為 $X_{m-1}$ 和 $Y_{n-1}$ 的子序列，且長度比 $Z_{k-1}$ 更長，即 $\|W\| \geqq k$ 。令序列 $W'=\langle w_{1}, ..., w_{k}, x_{m} \rangle$ ，則 $W'$ 亦為 $X$ 和 $Y$ 的共同子序列，且 $\|W\| \geqq k+1$ ，比 $Z$ 還要長，與 $Z$ 為最長共同子序列的假設互相矛盾。所以 $Z_{k-1}$ 必為 $X_{m-1}$ 和 $Y_{n-1}$ 的最長共同子序列。
- 若 $z_{k} \neq x_{m}$ ，則 $Z$ 為 $X_{m-1}$ 和 $Y$ 的最長共同子序列。若不是，則存在一個序列 $W$ 為 $X_{m-1}$ 和 $Y$ 的子序列，且 $\|W\| > k$ ，則此序列也會是 $X$ 和 $Y$ 的共同子序列（為什麼？），且長度比 $Z$ 還要更長，與 $Z$ 為最長共同子序列的假設互相矛盾。所以 $Z_{k-1}$ 必為 $X_{m-1}$ 和 $Y$ 的最長共同子序列。
- 若 $z_{k} \neq y_{n}$ ，則 $Z$ 為 $X$ 和 $Y_{n-1}$ 的最長共同子序列。理由同上。
- 寫出遞迴關係式
- 定義 $c[i, j]$ 為 $X_{i}$ 和 $Y_{j}$ 的LCS的長度，求 $c[m, n]$
- $c[i,j] = \left\{ \begin{array}{c l} 0 & \text{,if } i = 0 \text{ or } j = 0\\ c[i-1, j-1]+1 & \text{,if } i,j \neq 0 \text{ and } x = y \\ max(c[i-1, j], c[i, j-1]) & \text{,if } i,j \neq 0 \text{ and } x \neq y \end{array}\right.$
- 以bottom-up的方式求解
- 同樣的，LCS問題有很多的重複子問題，所以把已經解決過的子問題的答案存在表中，方便查表
- 除了找出LCS的長度外，我們也另外開一個表儲存LCS本身。 $X$ 和 $Y$ 的LCS或許不只一個，但最長的長度是固定的，我們只要可以找出其中一個LCS即可

    "use strict";
    class Array2D {
        constructor(xLen, yLen, init = 0){
            let temp = new Array(xLen);
            for(let i = 0; i < temp.length; ++i)
                temp[i] = new Array(yLen).fill(init);
            return temp;
        }
    }

    function LCS(X, Y){
        let c = new Array2D(X.length + 1, Y.length + 1, 0);
        let b = new Array2D(X.length + 1, Y.length + 1, 0);

        for(let i = 1; i <= X.length; ++i){
            for(let j = 1; j <= Y.length; ++j){
                if(X[i-1] === Y[j-1]){
                    c\[i\][j] = c\[i-1\][j-1] + 1;
                    b\[i\][j] = 0; // go up-left
                }
                else if(c\[i - 1\][j] > c\[i\][j - 1]){
                    c\[i\][j] = c\[i - 1\][j];
                    b\[i\][j] = 1; // go up
                }
                else{
                    c\[i\][j] = c\[i\][j - 1];
                    b\[i\][j] = -1; // go left
                }
            }
        }
        return {c, b};
    }

    // initially call print_LCS(X, b, X.length, Y.length)
    function print_LCS(X, b, i, j){
        if(i === 0 || j === 0) return;
        if(b\[i\][j] === 0){
            print_LCS(X, b, i - 1, j - 1);
            console.log(X[i-1]);
        }
        else if(b\[i\][j] === 1)
            print_LCS(X, b, i - 1, j);
        else
            print_LCS(X, b, i, j - 1);
    }

時間複雜度：O(m * n)：雙層for迴圈，一層跑m次一層跑n次，每次都花常數時間

## Optimal binary search trees

（待補，這太難QQ）

## Note