動態規劃基礎

本頁面主要介紹了動態規劃的基本思想，以及動態規劃中狀態及狀態轉移方程的設計思路，幫助各位初學者對動態規劃有一個初步的瞭解。

本部分的其他頁面，將介紹各種類型問題中動態規劃模型的建立方法，以及一些動態規劃的優化技巧。

引入

[IOI1994] 數字三角形

給定一個 \(r\) 行的數字三角形（\(r \leq 1000\)），需要找到一條從最高點到底部任意處結束的路徑，使路徑經過數字的和最大。每一步可以走到當前點左下方的點或右下方的點。

        7 
 8 
 1   0 
 7   4   4 
 5   2   6   5 

在上面這個例子中，最優路徑是 \(7 \to 3 \to 8 \to 7 \to 5\)。

最簡單粗暴的思路是嘗試所有的路徑。因為路徑條數是 \(O(2^r)\) 級別的，這樣的做法無法接受。

注意到這樣一個事實，一條最優的路徑，它的每一步決策都是最優的。

以例題裏提到的最優路徑為例，只考慮前四步 \(7 \to 3 \to 8 \to 7\)，不存在一條從最頂端到 \(4\) 行第 \(2\) 個數的權值更大的路徑。

而對於每一個點，它的下一步決策只有兩種：往左下角或者往右下角（如果存在）。因此只需要記錄當前點的最大權值，用這個最大權值執行下一步決策，來更新後續點的最大權值。

這樣做還有一個好處：我們成功縮小了問題的規模，將一個問題分成了多個規模更小的問題。要想得到從頂端到第 \(r\) 行的最優方案，只需要知道從頂端到第 \(r-1\) 行的最優方案的信息就可以了。

這時候還存在一個問題：子問題間重疊的部分會有很多，同一個子問題可能會被重複訪問多次，效率還是不高。解決這個問題的方法是把每個子問題的解存儲下來，通過記憶化的方式限制訪問順序，確保每個子問題只被訪問一次。

上面就是動態規劃的一些基本思路。下面將會更系統地介紹動態規劃的思想。

動態規劃原理

能用動態規劃解決的問題，需要滿足三個條件：最優子結構，無後效性和子問題重疊。

最優子結構

具有最優子結構也可能是適合用貪心的方法求解。

注意要確保我們考察了最優解中用到的所有子問題。

證明問題最優解的第一個組成部分是做出一個選擇；
對於一個給定問題，在其可能的第一步選擇中，假定你已經知道哪種選擇才會得到最優解。你現在並不關心這種選擇具體是如何得到的，只是假定已經知道了這種選擇；
給定可獲得的最優解的選擇後，確定這次選擇會產生哪些子問題，以及如何最好地刻畫子問題空間；
證明作為構成原問題最優解的組成部分，每個子問題的解就是它本身的最優解。方法是反證法，考慮加入某個子問題的解不是其自身的最優解，那麼就可以從原問題的解中用該子問題的最優解替換掉當前的非最優解，從而得到原問題的一個更優的解，從而與原問題最優解的假設矛盾。

要保持子問題空間儘量簡單，只在必要時擴展。

最優子結構的不同體現在兩個方面：

原問題的最優解中涉及多少個子問題；
確定最優解使用哪些子問題時，需要考察多少種選擇。

子問題圖中每個定點對應一個子問題，而需要考察的選擇對應關聯至子問題頂點的邊。

無後效性

已經求解的子問題，不會再受到後續決策的影響。

子問題重疊

如果有大量的重疊子問題，我們可以用空間將這些子問題的解存儲下來，避免重複求解相同的子問題，從而提升效率。

基本思路

對於一個能用動態規劃解決的問題，一般採用如下思路解決：

將原問題劃分為若干階段，每個階段對應若干個子問題，提取這些子問題的特徵（稱之為狀態）；
尋找每一個狀態的可能決策，或者説是各狀態間的相互轉移方式（用數學的語言描述就是 狀態轉移方程）。
按順序求解每一個階段的問題。

如果用圖論的思想理解，我們建立一個有向無環圖，每個狀態對應圖上一個節點，決策對應節點間的連邊。這樣問題就轉變為了一個在 DAG 上尋找最長（短）路的問題（參見：DAG 上的 DP）。

最長公共子序列

最長公共子序列問題

給定一個長度為 \(n\) 的序列 \(A\) 和一個長度為 \(m\) 的序列 \(B\)（\(n,m \leq 5000\)），求出一個最長的序列，使得該序列既是 \(A\) 的子序列，也是 \(B\) 的子序列。

子序列的定義可以參考子序列。一個簡要的例子：字符串 abcde 與字符串 acde 的公共子序列有 a、c、d、e、ac、ad、ae、cd、ce、de、ade、ace、cde、acde，最長公共子序列的長度是 4。

設 \(f(i,j)\) 表示只考慮 \(A\) 的前 \(i\) 個元素，\(B\) 的前 \(j\) 個元素時的最長公共子序列的長度，求這時的最長公共子序列的長度就是 子問題。\(f(i,j)\) 就是我們所説的狀態，則 \(f(n,m)\) 是最終要達到的狀態，即為所求結果。

對於每個 \(f(i,j)\)，存在三種決策：如果 \(A_i=B_j\)，則可以將它接到公共子序列的末尾；另外兩種決策分別是跳過 \(A_i\) 或者 \(B_j\)。狀態轉移方程如下：

\[ f(i,j)=\begin{cases}f(i-1,j-1)+1&A_i=B_j\\\max(f(i-1,j),f(i,j-1))&A_i\ne B_j\end{cases} \]

可參考 SourceForge 的 LCS 交互網頁來更好地理解 LCS 的實現過程。

該做法的時間複雜度為 \(O(nm)\)。

另外，本題存在 \(O\left(\dfrac{nm}{w}\right)\) 的算法¹。有興趣的同學可以自行探索。

int a[MAXN], b[MAXM], f[MAXN][MAXM];

int dp() {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (a[i] == b[j])
        f[i][j] = f[i - 1][j - 1] + 1;
      else
        f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
  return f[n][m];
}

最長不下降子序列

最長不下降子序列問題

給定一個長度為 \(n\) 的序列 \(A\)（\(n \leq 5000\)），求出一個最長的 \(A\) 的子序列，滿足該子序列的後一個元素不小於前一個元素。

算法一

設 \(f(i)\) 表示以 \(A_i\) 為結尾的最長不下降子序列的長度，則所求為 \(\max_{1 \leq i \leq n} f(i)\)。

計算 \(f(i)\) 時，嘗試將 \(A_i\) 接到其他的最長不下降子序列後面，以更新答案。於是可以寫出這樣的狀態轉移方程：\(f(i)=\max_{1 \leq j < i, A_j \leq A_i} (f(j)+1)\)。

容易發現該算法的時間複雜度為 \(O(n^2)\)。

C++Python

int a[MAXN], d[MAXN];

int dp() {
  d[1] = 1;
  int ans = 1;
  for (int i = 2; i <= n; i++) {
    d[i] = 1;
    for (int j = 1; j < i; j++)
      if (a[j] <= a[i]) {
        d[i] = max(d[i], d[j] + 1);
        ans = max(ans, d[i]);
      }
  }
  return ans;
}

a = [0] * MAXN
d = [0] * MAXN
def dp():
    d[1] = 1
    ans = 1
    for i in range(2, n + 1):
        for j in range(1, i):
            if a[j] <= a[i]:
                d[i] = max(d[i], d[j] + 1)
                ans = max(ans, d[i])
    return ans

算法二²

當 \(n\) 的範圍擴大到 \(n \leq 10^5\) 時，第一種做法就不夠快了，下面給出了一個 \(O(n \log n)\) 的做法。

回顧一下之前的狀態：\((i, l)\)。

但這次，我們不是要按照相同的 \(i\) 處理狀態，而是直接判斷合法的 \((i, l)\)。

再看一下之前的轉移：\((j, l - 1) \rightarrow (i, l)\)，就可以判斷某個 \((i, l)\) 是否合法。

初始時 \((1, 1)\) 肯定合法。

那麼，只需要找到一個 \(l\) 最大的合法的 \((i, l)\)，就可以得到最終最長不下降子序列的長度了。

那麼，根據上面的方法，我們就需要維護一個可能的轉移列表，並逐個處理轉移。

所以可以定義 \(a_1 \dots a_n\) 為原始序列，\(d_i\) 為所有的長度為 \(i\) 的不下降子序列的末尾元素的最小值，\(len\) 為子序列的長度。

初始化：\(d_1=a_1,len=1\)。

現在我們已知最長的不下降子序列長度為 1，那麼我們讓 \(i\) 從 2 到 \(n\) 循環，依次求出前 \(i\) 個元素的最長不下降子序列的長度，循環的時候我們只需要維護好 \(d\) 這個數組還有 \(len\) 就可以了。關鍵在於如何維護。

考慮進來一個元素 \(a_i\)：

元素大於等於 \(d_{len}\)，直接將該元素插入到 \(d\) 序列的末尾。
元素小於 \(d_{len}\)，找到 第一個 大於它的元素，用 \(a_i\) 替換它。

為什麼：

對於步驟 1：

由於我們是從前往後掃，所以説當元素大於等於 \(d_{len}\) 時一定會有一個不下降子序列使得這個不下降子序列的末項後面可以再接這個元素。如果 \(d\) 不接這個元素，可以發現既不符合定義，又不是最優解。
對於步驟 2：

同步驟 1，如果插在 \(d\) 的末尾，那麼由於前面的元素大於要插入的元素，所以不符合 \(d\) 的定義，因此必須先找到 第一個 大於它的元素，再用 \(a_i\) 替換。

步驟 2 如果採用暴力查找，則時間複雜度仍然是 \(O(n^2)\) 的。但是根據 \(d\) 數組的定義，又由於本題要求不下降子序列，所以 \(d\) 一定是 單調不減 的，因此可以用二分查找將時間複雜度降至 \(O(n\log n)\).

參考代碼如下：