# Dynamic Programming
> 長江後浪推前浪，一代新人換舊人

何謂動態規劃(Dynamic Programming, dp ) ?
> Programming 是指寫程式嗎 ?
實際上是 integer programming / nonlinear programming
(線性 / 非線性規劃)
帶有最佳化的意思。

( 摘要自 [交大開放式課程](https://www.youtube.com/watch?v=359YMyqbEG4) )

Dynamic Programming (動態規劃) 的基礎是先前提到的 divide and conquer (分治法)。
當切割出來的小部分具有某種規律或相似性，一而再再而三地出現，
我們就利用當前已知的結果去推算後續的答案。

### dp 的步驟
1. 定義狀態 ( dp[i] 的意義 ? )
2. 找出轉移式 ( 遞迴式 )
3. 釐清初始狀態 ( 如何出發 ? 終止條件 ? )

### 費氏數列

$$
F_0 = 0
$$
$$
F_1 = 1
$$
$$
F_n = F_{n-1} + F_{n-2}, \quad n \geq 2
$$

這裡的 f(n) 及為 dp[n]，
所以轉移式就是 dp[i] = dp[i - 1] + dp[i - 2]，
在 n = 2 之後每一項的值是前兩項值的總和，
因此，只要依序取得前幾項的答案，
我們就能往後推算，
時間複雜度為 O(n)。

**跟遞迴的比較 :**
若直接遞迴，不將資料存到陣列中，
會重複算到同樣顏色的部分，例如 f(3)，
現在我們第一次計算時就將資料存起來，
第二次走到時將資料取出即可，不用繼續往下遞迴，
這就是動態規劃的概念 : 以空間換取時間，時間複雜度從 O(n^2^) 降到 O(n)。

**跟貪心的比較 :**
在學習的過程，看到某些對於動態規劃的描述總覺得似曾相識，
在查詢過程看到了這篇文章，在此推薦:
https://ithelp.ithome.com.tw/m/articles/10331177

### [AtCoder - Frog 1](https://atcoder.jp/contests/dp/tasks/dp_a)
給定石頭總數 N 與 每個石頭的高度 hi，
這隻青蛙最開始在第 1 顆石頭，一次只能跳格或兩格，
從高度 hi 的石頭跳到高度 hj 的石頭，需要花費 ∣ hj - hi ∣
試求從第 1 顆石頭跳到第 N 顆石頭的最小花費

**假設現在青蛙在第 x 顆石頭，他的來源有兩種選擇 :**
1. 從第 x - 1 顆石頭跳過來
2. 從第 x - 2 顆石頭跳過來

**定義 dp[x] 是走到第 x 格的總花費 :**
1. 跳到第 x - 1 顆石頭累積的花費 dp[x - 1] + 從第 x - 1 顆石頭跳過來的花費 ∣ hx - h~x-1~ ∣
2. 跳到第 x - 2 顆石頭累積的花費 dp[x - 2] + 從第 x - 2 顆石頭跳過來的花費 ∣ hx - h~x-2~ ∣

**選擇其中最小的花費 :**
用 int high[N + 1] 儲存 h~i~

**轉移式 :**

dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));

用一個迴圈從 int i = 1 開始跑，跑到 i = x 時 dp[x - 1] 跟 dp[x - 2] 皆已被處理，
因此不必擔心前面的選擇並非最優解。

**最後檢查初始跟終止的狀態 :**
* 初始 : dp[1] = abs(high[1] - high[0]);
* 終止 : i = N, dp[N] 是所求

**程式碼解釋 :**
題目是從 1 開始編號，但在解題時我從 0 開始，
所以 dp[1] 實際上對應的是第 2 顆石頭，最後輸出 dp[n - 1]。
這點可依個人習慣調整。
之所以把 dp[1] = abs(high[1] - high[0]) 獨立出來，
是因為第 2 顆石頭只能是從第 1 顆跳過來，不會是從第 -1 顆，
也避免戳到 dp[-1] 。

code :

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n ; cin >> n;
    int high[n];
    int dp[n] = {0};

    for(int i = 0 ; i < n ; i++){
        cin >> high[i];
    }

    dp[1] = abs(high[1] - high[0]);
    for(int i = 2 ; i < n ; i++){
        dp[i] = min(dp[i - 1] + abs(high[i] - high[i - 1]), dp[i - 2] + abs(high[i] - high[i - 2]));
    }
    cout << dp[n - 1];
    return 0;
}

### [AtCoder - Frog 2](https://atcoder.jp/contests/dp/tasks/dp_b)
給定石頭總數 N 、 每個石頭的高度 hi 、 青蛙每次可以往後跳 K 格
這隻青蛙最開始在第 1 顆石頭，一次可以跳 1, 2, 3 ...... K格，
從高度 hi 的石頭跳到高度 hj 的石頭，需要花費 ∣ hj - hi ∣
試求從第 1 顆石頭跳到第 N 顆石頭的最小花費
這題跟上題不同的是
青蛙可以往後跳的次數不是固定一格或兩格，而是隨著輸入改變。

**假設現在青蛙在第 x 顆石頭，他的來源有 K 種選擇 :**
* 從第 x - 1 顆石頭跳過來
* 從第 x - 2 顆石頭跳過來
.
.
.
* 從第 x - K 顆石頭跳過來

用變數 min1 去找出所有可能的 dp[x - 1] + ∣ hx - h~x-1~ ∣ 最小值
最後再放到 dp[i] 中。

code :

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, k; cin >> n >> k;
    int hight[n], dp[n];
    for(int i = 0 ; i < n ; i++){
        cin >> hight[i];
    }
    
    dp[0] = 0;
    dp[1] = abs(hight[1] - hight[0]);

    for(int i = 2 ; i < n ; i++){
        int min1 = dp[i - 1] + abs(hight[i] - hight[i - 1]);
        for(int j = 2 ; j <= k && j <= i ; j++){
            int now = dp[i - j] + abs(hight[i] - hight[i - j]);
            min1 = min(now, min1);
        }
        dp[i] = min1;
    }

    cout << dp[n - 1];
    return 0;
}

### [AtCoder - Vacation](https://atcoder.jp/contests/dp/tasks/dp_c)
Taro 在計畫他為期 N 天的暑假要幹嘛
他每天會選擇三件事中的一件做，並獲得對應的快樂值
1. 在海邊游泳，獲得 a 點快樂值
2. 在山裡抓 bug，獲得 b 點快樂值
3. 在家寫作業，獲得 c 點快樂值
每天的 a b c 是不同的，且 Taro 不會連續兩天做同一件事，
請找出快樂度最大可以是多少。
輸入 : 第一行是天數 N ，後面有 N 行，每行是每天的 a b c
**假設 Taro 在第 i 天做了第 1 件事，那第 i - 1 天有兩種可能 :**
* Taro 做第 2 件事
* Taro 做第 3 件事

假設 Taro 在第 i 天做了第 2 件事，那第 i - 1 天有兩種可能 :
* Taro 做第 1 件事
* Taro 做第 3 件事

假設 Taro 在第 i 天做了第 3 件事，那第 i - 1 天有兩種可能 :
* Taro 做第 1 件事
* Taro 做第 2 件事

這是因為 Taro 不會連續兩天做同一件事

**定義 dp[i][j] 是第 i 天做第 j 件事所累積的最大快樂度 :**
dp[i][j] = 第 i - 1 天做某件事的快樂度 + 第 i 天做 j 件事的快樂度

**選擇其中最大的快樂度 :**
用 int happy[N + 1][4] 儲存第 i 天做第 j 件事得到的快樂度

**轉移式 :**
1. dp[i][1] = max(dp[i - 1][2], dp[i - 1][3]) + happy[i][1]
2. dp[i][2] = max(dp[i - 1][1], dp[i - 1][3]) + happy[i][2]
3. dp[i][3] = max(dp[i - 1][1], dp[i - 1][2]) + happy[i][3]

**最後檢查初始跟終止的狀態 :**
* 初始 : dp[1][1] = happy[1][1]; dp[1][2] = happy[1][2]; dp[1][3] = happy[1][3];
* 終止 : i = N, max(dp[N][1], max(dp[N][2], dp[N][3])) 是所求

code :

#include<iostream>
using namespace std;
int main(){
    int N ; cin >> N;
    int happy[N + 1][3 + 1];
    int dp[N + 1][3 + 1];
    for(int i = 1 ; i <= N ; i++){
        cin >> happy[i][1];
        cin >> happy[i][2];
        cin >> happy[i][3];
    }

    dp[1][1] = happy[1][1];
    dp[1][2] = happy[1][2];
    dp[1][3] = happy[1][3];

    for(int i = 2 ; i <= N ; i++){
        dp[i][1] = max(dp[i - 1][2], dp[i - 1][3]) + happy[i][1];
        dp[i][2] = max(dp[i - 1][1], dp[i - 1][3]) + happy[i][2];
        dp[i][3] = max(dp[i - 1][1], dp[i - 1][2]) + happy[i][3];
    }

    cout << max(dp[N][1], max(dp[N][2], dp[N][3]));
    return 0;
}

## Edit distance
Edit distance 就是將 s1 改成與 s2 相同的最小操作數。
假設現在有兩字串 s1 與 s2，
dp[i][j] 代表將 s1 前 i 個字元（index 為 0 ~ i - 1），
改成與 s2 中 index 前 ｊ 個字元（index 為 0 ~ j - 1）相同的最小操作數。
dp 從 0 開始，恰對應空字串（s1 與 s2 的前 0 個字元）。
在操作時，我們考慮 s1[i - 1] 與 s2[j - 1] 這兩個選取範圍末端的字元。
有以下幾個操作可使用：
1. 新增一個字元
2. 刪除一個字元
3. 將一個字元轉變成其它字元（取代）

**對於 s1[i - 1] != s2[j - 1]，我們可以用以下三種方式得到 dp[i][j] :**
1. 刪除 s1 的第 i - 1 個字元，例如 abc**d** 與 abc，dp[i][j] = dp[i - 1][j] + 1（增加一個操作數，變為　dp[i - 1][j]）的狀態。
2. 將 s1 新增一個與 s2[j - 1] 相同的字元，例如 abc 與 abcd，dp[i][j] = dp[i][j - 1] + 1（增加一個操作數，變為　dp[i][j - 1]）的狀態。
3. 將 s1[i - 1] 變成 s2[j - 1]，例如 abc**d** 與 abc**e**，dp[i][j] = dp[i - 1][j - 1] + 1（增加一個操作數，變為 dp[i - 1][j - 1]）的狀態。

**對於 s1[i - 1] == s2[j - 1]，dp[i][j] = dp[i - 1][j - 1]，不用增加操作數**
我們將以上幾種方式取最小值（min）

**最後檢查初始跟終止的狀態 :**
* 初始：dp[0][i] 將 s1 新增 i 個與 s2 相同的字元
* 初始：dp[i][0] 將 s1 刪除 i 個字元
* 終止：dp[s1.size()][s2.size()] 是所求

**code :**

#include<bits/stdc++.h>
using namespace std;
int main(){
string s1, s2;
cin >> s1 >> s2;

int l1 = s1.size(), l2 = s2.size();
int dp[l1 + 1][l2 + 1];

for(int i = 0 ; i <= l1 ; i++){
    dp[i][0] = i;
}
for(int j = 0 ; j <= l2 ; j++){
    dp[0][j] = j;
}

for(int i = 1 ; i <= l1 ; i++){
    for(int j = 1 ; j <= l2 ; j++){
        dp[i][j] = dp[i][j - 1] + 1;
        dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (s1[i - 1] != s2[j - 1]));
    }
}

cout << dp[l1][l2];
return 0;
}

## LIS
最長遞增子序列 (Longest Increasing Subsequence, LIS)
顧名思義是在數列中找出數值與相對位置皆遞增的子序列中最長的一個
例如 1 2 8 3 9 5 的最長遞增子序列有
1 2 3 5
1 2 8 9
最大長度是 4

在這裡探討 dp 的解法，也有二分搜的解法

我們的目標是找出最長遞增子序列的長度 (用 ans 儲存)
建議對照 code 的部分

**dp[i] 代表的是以 nums[i] 為結尾的最長遞增子序列**
每次選定結尾 i
再用 j 從 0 到 i - 1
檢查原本以 nums[j] 為結尾的遞增序列
再加上 nums[i] 是否依然符合遞增

如果 nums[j] < nums[i] 代表 nums[i] 接在 nums[j] 後依然符合遞增
因此 dp[i] 可以是 dp[j] + 1
我們在從其中挑選出最大的長度保存下來
**轉移式為 dp[i] = max(dp[i], dp[j] + 1) (num[j] < num[i] 且 j < i)**

**dp[] 的初始值是 1** ， 因為是以一個數字為基準累加
假設 1 3 5 ， i = 1, j = 0 時 1 3 符合遞增，此時的 dp[i] 應該要是 max(1, 1 + 1)

時間複雜度 : O(n^2^)

code :

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, ans = 1;
    cin >> n;
    int nums[n + 5], dp[n + 5]; 
    for(int i = 0 ; i < n ; i++){
        cin >> nums[i];
        dp[i] = 1; //或 fill(dp, dp + n, 1)
    }

    // LIS
    for(int i = 1 ; i < n ; i++){
        for(int j = 0 ; j < i ; j++){
            if(nums[j] < nums[i]){
                dp[i] = max(dp[i], dp[j] + 1);
                ans = max(ans, dp[i]);
            }
        }
    }
    cout << ans;
    return 0;
}

參考資料 :
[LIS 最長遞增子序列 解法探究](https://hackmd.io/@TiIfch0PSMaUEa8YFQKXDg/BJgqpu_k6)