動態規劃 Lecture 1A: 問題與子問題

演算法題目

什麼是「題目」(Problem)？在競技程式裡頭，通常我們指稱的「題目」，都有著某種固定的格式：對於某種制定的輸入格式（Input），你需要撰寫一支程式，在有限的時間內產生一個正確的輸出（Output）。

題目 (Problem) vs 樣例 (Instance)

許多教科書上面會提到 “Instance” 一詞，其實對我們來說其實就是一組「輸入」。 從現在開始我們將一個「問題」定義為：一個題目 加上 一組輸入。

問題與子問題

在提出解決一道題目的演算法時，我們有時候會專注於將一個「問題」，分成許多輸入規模更小的「子問題」。通過解決這些子問題得到的答案，我們得以拼湊出原本問題的答案。若一類演算法從解決「子問題」到解決原本的「問題」的過程滿足一些條件，那麼我們對於這類型的演算法給予不同的描述：

• 子問題不重複，不需把過程記錄下來 $\to$ 分而治之 Divide and Conquer
• 子問題重複，且我們把過程記錄下來 $\to$ 動態規劃 Dynamic Programming

舉例來說，若我們想要解決 $(n, a, b, c)$ 的一組切緞帶問題，一個可行的切入點會是：考慮任何一個合法的切緞帶方式，其切出來最後一段的長度僅可能是 $a$、$b$ 或是 $c$。此時我們可以發現，對於長度 $a$、$b$ 或 $c$ 的任何一種情形，若把前面的片段通通加起來，長度恰好會是 $n-a, n-b$ 以及 $n-c$。

因此，若我們定義 $\OPT_{a, b, c}(n)$ 為能夠合法地把長度為 $n$ 的緞帶切成長度為 $a, b, c$ 三者之一的最大段數，我們可以把答案寫成以下的遞迴形式：

當然，為了讓遞迴計算能有個基礎，我們必須要加上遞迴初始條件：

這個初始條件頗重要的，$-\infty$ 代表的是「無解」。在動態規劃的演算法裡頭，我們偶爾會稱呼一個子問題 $(n’, a’, b’, c’)$ 叫做一個 狀態 (state)，而稱呼遞迴關係式為 狀態轉移 (state transitions)。若我們有足夠的記憶體將所有計算的過程通通記錄下來，而且可以 $O(1)$ （常數時間）存取任何子問題的答案，那麼我們可以用相當單純的方式估計該演算法的時間複雜度：

以切緞帶的例子來說，所有會被遞迴式展開到的子問題 $\OPT_{a, b, c}(x)$，其 $a, b, c$ 之值皆不變，而 $x$ 取值可能為 $1, \cdots, n$（我們在這裡不考慮 $x\le 0$，因為邊界初始條件可以被輕易處理掉）。所以狀態總數是 $O(n)$ 種，狀態的轉移只要計算三個數字的最大值、並加上 1 即可，轉移只要花費 $O(1)$ 時間。

記錄計算過的狀態也相當單純──我們可以用一個陣列 $\DP[1\ldots n]$ 直接進行存取就好，因此我們可以得到 $O(n)$ 時間的遞迴演算法。直接的實作如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 10000;
int dp[4001];
bool used[4001];

int maximumCutRibbon(int n, int a, int b, int c) {
    if (n < 0) return -INF;
    if (n == 0) return 0;
    if (used[n]) return dp[n];
    
    // 標記說這個狀態已經被計算過，這樣下次就不會重新遞迴呼叫了。
    used[n] = true;

    // 找出三個數字的最大值。
    dp[n] = 1 + maximumCutRibbon(n-a, a, b, c);
    dp[n] = max(dp[n], 1 + maximumCutRibbon(n-b, a, b, c));
    dp[n] = max(dp[n], 1 + maximumCutRibbon(n-c, a, b, c));
    return dp[n];
}

// 下面是讀取輸入、計算並輸出的部份
int main() {
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    cout << maximumCutRibbon(n, a, b, c) << endl;
    return 0;
}