DP 的概念

DP 是什麼?

當我們在解決問題時，常常並不能一步到位，但大問題能夠切成結構相似的小問題，藉由小問題的組成，解回原本的大問題。

有沒有感覺很耳熟? 沒錯，動態規劃 ( Dynamic programming 後簡稱為 dp ) 跟遞迴很相似，都是把大問題分而治之的一種想法。

為什麼要用 DP?

既然dp跟遞迴很相似，為什麼要學dp? 考慮費氏數列的計算 $F_i + F_{i+1} = F_{i+2}$

若是使用遞迴可能會寫出如下代碼

long long f(int x) {
    if (x == 0) return 0;
    if (x == 1) return 1;

    return f(x-1) + f(x-2);
}

但實際運行後會發現，到第 $f(42)$ 以上運行時間就越變越慢，為甚麼? 分析一下就會發現，這段程式碼複雜度為 $\mathcal{O}(\sum^{n}_{i=1}F_i)$ ，但 $F_i$ 的增長速度很快，這段程式的運行效率不是很好。

那要怎麼優化? 這就是 dp 出場的時候了! 觀察一下會發現，上面的程式碼在計算 $f(i-1)$ 時 $f(i-2)$ 其實已經被算過了，如果可以記起來的話，就不用那麼麻煩了... 那不如就記起來?

long long dp[mx];

long long f(int x) {
    if (x == 0) return 0;
    if (x == 1) return 1;
    if (dp[x] ! = 0) return x;
	dp[x] = f(x-1) + f(x-2)
	
    return dp[x];
}

才多了三行... 會有什麼幫助嗎 (當然會 足足多了60%) 我們來分析一下，每個數字最多計算兩次，所以這個優化過的遞迴複雜度為 $\mathcal{O}(N)$ ! 算到 $10^7$ 都不是問題!

疑等等，剛剛不是說 $F_i$ 增長速度很快，$F_{10^7}$ 可以用 long long 存嗎? 當然不行，所以大多數 dp 題目，尤其是涉及計數的，通常會要求模某個 int 以內的大數，但那是後話了。

剛剛優化的程式碼，是遞迴與 dp 想法的結合，又名 "記憶化搜尋"、 "Top-down"，Top-down... 難道有 Buttom-up? 沒錯!

long long f(x) {
	vector<int> dp(x+1);
	dp[0] = 0;
	dp[1] = 1;
	for (int i=2;i<=x;i++) {
		dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[x];
} 

Top-down 是以大問題的角度，考慮如何切割小問題，再解決小問題，最後將小問題合併解決大問題，以遞迴實作。 Buttom-up 是先解決小問題，再組合成大問題，以迭代實作。 通常 Top-down 比較符合思考問題的過程，比較直觀，但 Buttom-up 以遞迴實作，通常速度較快。 這兩個是 dp 主要實作方法。

DP 到底是什麼?

講了那麼多，感覺還是對 dp 的感覺不實際，好像是一種優化，又是什麼小問題結合成大問題，到底 dp 是什麼?

由於發展到現在 dp 算是一個很大的主題，很難一言以蔽之，但 dp 通常有如下步驟:

1. 定狀態 ( 找到相同結構的問題 )
2. 想轉移 ( 將子問題合併到原問題 )
3. 優化 ( 有些單調性、dp 的函式性質能將演算法複雜度壓低 )

狀態，就是切出來的問題，用 array 或是其他資料結構儲存，是一種空間換時間的做法。 轉移，就是將子問題合併的過程，有些只要常數時間，但有些轉移需要的子問題數量跟資料大小有關係，可能是多維的。

而對於狀態 $a$ 維，轉移 $b$ 維的 dp ，表示為 $aD/bD$ dp

總而言之，dp 是以空間換取時間的戰術，老蔣的遺志