DP

最大連續區間和

問題敘述 : 第 \(i\) 個賭局可以贏得 \(a_i\) 塊錢，以正數與負數表示表示贏錢與輸錢
選任意一局開始，連續的賭局當中最多可以贏得多少錢

題目的意思等價於求一個序列中子區間的最大連續和

分析每個 \(a_i\) 會發現只有兩種情況，一種是包含在答案的子序列中(必須是連續的)，另一種是它是新的連續子序列的開頭。

而其中不包含在答案的子序列中就不必討論，只討論包含在答案的子序列中。

可以把 \(dp[i][j]\) 定義成表示第 \(i\) 項在兩種情況當中前 \(i\) 項的最大連續和
其中 \(j\) 代表前頁的第幾種情況
若 \(j=0\) 代表第 \(i\) 項包含在答案的子序列中
若 \(j=1\) 代表第 \(i\) 項是新的連續子序列的開頭
則可以求出轉移式
\[ \begin{cases} dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + a[i] \\ dp[i][1] = a[i] \end{cases} \]

初始化

\[ \begin{cases} dp[0][0] = 0 \\ dp[0][1] = a[0] \end{cases} \]

為何是
\[ \begin{cases} dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + a[i] \\ dp[i][1] = a[i] \end{cases} \]
因為對於 \(dp[i][0]\)(這一項必取) 來說，它包含前幾項的最好，所以它會是 \(dp[i-1][0]\)(前一項也取) 或者是 \(dp[i-1][1]\)(前一項是第一項) 的 \(max\) 加上他自己

而對於 \(dp[i][1]\) 來說，他自己就是第一項，因此它的值 (對第 \(i\) 項來說 \(i\) 就是第一個) 會是 \(a[i] + 0\)

在那之前要先補充二分搜的 \(LIS\) 作法

從 \(1\) 到 \(n\) 遍歷 \(A\) 的每個元素，每次與 \(X\)(當前LIS) 裡的元素進行檢查，
若是比結尾元素大就加入，若沒有就使用 \(lower\_bound\) 取代原本的位置。

sample code

從 \(1\) 到 \(n\) 遍歷 \(A\) 的每個元素，每次與當前 LIS 裡的元素進行檢查，
若是比結尾元素大就加入，若沒有就使用 \(lower\_bound\) 取代原本的位置。

vector<int> getLIS(vector<int> a){
    vector<int> lis;
    for(int i : a){
        if(lis.empty() || lis.back() < i)    lis.push_Back(i);
        else      *lower_bound(lis.begin(), lis.end(), i) = i;
    }
    return lis;
}

LCS to LIS

為何需要轉換?

• 求出 LCS 的時間、空間複雜度都是 \(O(N^2)\) ，使用滾動陣列技巧，可將空間複雜度降至 \(O(N)\)
• 求出 LIS 的時間複雜度 \(O(N^2)\) ，空間複雜度 \(O(N)\) ，但其中 LIS 的時間複雜度可以使用二分搜 (lower_bound) 優化成 \(O(N\log N)\)

怎麼轉換?

• LIS 轉 LCS ：令原序列 A 排序後變成 B 。 A 和 B 的 LCS ，就是 A 的 LIS 。

• LCS 轉 LIS ：將序列 A 和 B 當中的相同字母配對通通找出來，表示成位置數對，以特殊規則(Counting sort)排序，然後找到 LIS ，就是 A 和 B 的 LCS 。

LCS 轉 LIS 於是你會發現二維平面的 LCS 會變成二維平面的 LIS

二維平面的 LIS 聽起來複雜度並沒有比較好，因此
所有數對：第一維由小到大排序；當第一維平手，則第二維由大到小排序。

排序之後，原本數對們的 2D LIS ＝第二維的 1D LIS

於是就可以將LCS在經過一連串的預處理之後變成 \(O(n \log n )\) 的時間複雜度。

Edit distance

ex :
\(string_1\) : horse
\(string_2\) : ros
所謂 Edit distance 就是 \(string_1\) 最少要幾步才能變成 \(string_2\) ，而其中每一步可以是 “新增”、“刪除” 或是 “取代”。所以第一個範例 horse 經過了

1. 用 r 取代 h
2. 把中間的 r 刪除
3. 把最後的 e 刪除

就可以得到 ros ，共花了 3 步 (3 就是答案)。

通常如果是需要去比對兩個字串的題目，我們會定義狀態為一個二維陣列 \(dp[i][j]\)
\(dp[i][j]\) 為 \(string_1\) 中前 \(i\) 個字元的字串和 \(string_2\) 中前 \(j\) 個字元的字串的 Edit Distance
而我們知道子問題後，我們的答案就顯而易見是 \(dp[len(string_1)][len(string_2)]\)

而很重要的初始化會發現，每個字串到空字串之間最快的路徑就是直接"消除"，因此會有以下初始化 :
\[ \begin{cases} dp[i][0] = i \ , i \leq len(string_1)\\ dp[0][j] = j \ , j \leq len(string_2)\\ \end{cases} \]

然後我們只需要思考， \(dp[i][j]\) 可以怎麼轉移。
分別有兩點

• 當 \(string_1\) 第 \(i\) 個字和 \(string_2\) 第 \(j\) 個字相同時，則 \(dp[i][j] = dp[i-1][j-1]\) ，因為此時不需要做任何操作即相同。
• 當 \(string_1\) 第 \(i\) 個字和 \(string_2\) 第 \(j\) 個字不同時，則會有三個操作

1. 刪除 : 刪除第 \(i\) 個字，此時 \(dp[i][j]\) 為 \(dp[i-1][j]+1\) (後面的 +1 代表刪除)
2. 新增 : 新增第 \(i\) 個字，此時 \(dp[i][j]\) 為 \(dp[i][j-1]+1\) (後面的 +1 代表新增)
3. 取代 : 把 \(string_1\) 的第 \(i\) 個字變成 \(string_2\) 的第 \(j\) 個字，此時 \(dp[i][j]\) 狀態方程為 \(dp[i-1][j-1]+1\) (後面的 +1 代表取代)。

所以可以總結出狀態轉移方程為 \(dp[i][j]= min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1\)

LCS vs LIS vs Edit distance

首先會思考到，由於只能挑跟不挑，所以可以暴力枚舉每一個數字是否再答案裡面，然後再思考一下時間複雜度就會發現，需要的量級是指數級的，為 \(O(2^n)\) 所以 \(n\) 稍微大一點就很容易TLE

所以會需要使用到動態規劃，令 \(dp[i][j]\) 表示 \(arr\) 中前 \(i\) 個元素的子集和等於 \(j\) 的情況，則

若 \(arr[i] > j\) ，則 \(arr[i]\) 不在子集 \(subset\) 中。
若 \(arr[i] \le j\) , 則有以下兩種情況：一種情況是 \(arr[i]\) 不在子集 \(subset\) 中，則 \(dp(i, j) = dp(i-1, j)\) 一種情況是 \(arr[i]\) 在子集 \(subset\) 中，則 \(dp[i][j]= dp[i-1][j-arr[i]]\)

這樣就有了這個問題的子結構問題，因此，只需要確定初始情況即可
而初始情況即為對於 \(i=0,1,2,...,n\) ,有 \(dp[i][0]=True\) , 對於 \(j=1,2,...,M\) , 有 \(dp[0][j]=False\)

然後你就會發現代碼會長這樣

for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(j<arr[i])
                dp[i][j] = dp[i-1][j]
            else
                dp[i][j] = dp[i-1][j] | dp[i-1][j-S[i-1]]

而倘若你需要知道 subset 是由那些 sub_element 組合成的，則可以把 DP 的真值表印出來，參考上次 LCS 的回朔法使用查詢。

參考甲文

0/1背包 bitset 優化

例題 : zerojudge a416

題目敘述轉化 : 把一列大小為 \(n\) 整數序列分成兩個子集且讓兩個子集的 sum 最接近

那這邊我們就可以用到 bitset 的思想，首先先介紹一下 bitset 的用法和為何使用 bitset :

• 對於 bitset，它儲存的是二進制數位。
• bitset 就像一個 bool 類型的陣列一樣，但是有空間優化：bitset 中的一個元素只占 1 bit，相當於一個 char 所占空間的八分之一。
• bitset 中的每一個元素都可以被單獨存取，例如一個叫做 foo 的 bitset，foo[3] 存取了它的第四個元素，這點類似於陣列。
• bitset 有一個特性：整數類型和 bool 陣列都可以轉化為 bitset。
• bitset 的大小在編譯前就需要確定 (程式碼中使用常數宣告大小) 。

更多具體用法以及魔法

對於這道題，我們用 bitset 來替代 DP，bits[j] 的含義與 DP[j] 的含義相同。就是是否有這樣的一個子集的總和是 \(j\)

假設現在有一個數組 {2,3,5,2,3,5} 很明顯可以看出它的解答是 \(2+3+5=10\) 那對於我們的 bitset 數組會長這樣

bitset<N> dp(1);
dp {1} //代表0可以選 (有一個子集合是0)
dp {101} //加入'2' 了，把原本所有1的bit左移兩個 現在代表 '2' 和 '0' 都可以有子集合
dp {101101} //加入'3'了，把原本所有1的bit左移三個 '0' '2' '3' '5' 都有子集合
dp {10110101101} //加入'5'了，把原本所有1的bit左移五個 
//依此類推

到最後只要詢問 \(sum/2\) 開始往左右邊遍歷就可以知道答案了。

• 再次拿遞迴數學式來舉例
• \(f(n)=f(n-1)+f(n-2)\)
• 可以看出計算每一項在計算時，只會用到\(dp[n],dp[n-1],dp[n-2]\)
• 因此原本需要開到\(N\)大的空間數組就不需要開，只需要開3個變數
• 只能用bottom-up計算，只需要三個變數交替使用\(cur,pre,ppre\)

int cur,pre=1,ppre=0;
for(int i=2;i<=n;i++)
    cur=pre+ppre,ppre=pre,pre=cur;

滾動DP結論

• 用來節省空間，常常可以節省一個維度
• 不是所有DP都可以滾動
• 用於bottom-up，單次計算
• 從轉移式中看計算每一項所需要用到的子狀態是否有跟著遞增(算到後面，前面的狀態就不會再被使用)

直接實作最後一題 : 二階樓梯記數問題

一個\(n\times n\)方格棋盤，從左上角走到右下角，每次只能往右走一格或者往下走一格。請問有幾種走法？
example :

第一步 分割問題 會發現對於任何一個方格來說，只可能「從上走來」或者「從左走來」，答案是兩者相加，也就是說可以從上方以及左方的方格步數推算出當前這格的步數。

設計轉移式 \(dp[i][j]\)代表走到當前 \(i\), \(j\) 格有幾種方法，因此\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)

然後這時候就會發現，他的轉移式只需要用到\(i\)的前一項或者是\(j\)的前一項，那是否可以節省空間呢

答案是必然的，如果不需要儲存所有問題的答案，只想要得到其中一個特定問題的答案，那只需要一維陣列就夠了，也就是 O(N) 空間。

for (int i=1; i<N; i++)
		for (int j=1; j<N; j++)
			f[j] += f[j-1];

就成功的作出了空間優化了

bonus

關於最大連續子區間和

同時會發現到dp轉移式裡面只轉移 \(i\) 以及 \(i-1\) ，這可以使用 rolling 壓縮空間複雜度，因此會變成這樣。

    dp[i&1][0] = max(dp[(i-1)&1][0], dp[(i-1)&1][1]) + m;
    dp[i&1][1] = m;

而時間複雜度會是\(O(n)\)