【C++】競程筆記（DP：Top Down & Bottom up）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

Stack overflow

Stack overflow 是一個 IT 論壇，然後在程式當中也會發生這種情形XD，有時候說 Stack overflow 也是一個雙關語。

至於 Stack overflow 是什麼呢？字面上意思就是堆疊溢位，是指程式使用過多的記憶體時導致呼叫堆疊產生的溢位。通常最常見的原因就是因為函式呼叫中使用到遞迴，導致遞迴過深。

遞迴的原理就是使用到了 stack 這個資料結構，每次呼叫會把值堆入堆疊，直到終止條件再將這些值一個一個拿出來。

94 . [Tutorial] 別離太遠

Problem Source：https://oj.ntucpc.org/problems/94

這題可以體會一下什麼叫做 stack overflow。

題目沒有給你 N = 1 跟 N = 2 的情況，但這兩個情況很簡單，稍微推算一下就可以知道方法數了。

N = 1：由於只有一個，所以方法數是 1。
N = 2：有 1 跟 2，但必須選擇 1 跟 2，因為編號差 2 - 1 = 1，所以只有一種方法。

題目後面很佛心還給你了 N = 3 跟 N = 4 的方法數，分別是 2 跟 3。

這時候將方法數排在一起看，就會發現有所端倪： $1, 1, 2, 3$ ，疑！？這不是費氏數列的長相嗎？

但在此之前，題目說 $N$ 可能高達 $10^7$ ，費氏數列的成長速度極快，就算用 unsigned long long 都會溢位，這時候題目告訴你可以將方法數除以 $10^9 + 7$ 的餘數，於是程式碼就可以這樣寫了：

#include <iostream>

using namespace std;

const int MOD = 1000000007;

int dp[10000010] = {0};

int solve(int N){
    if (N <= 2) return 1;
    if (dp[N] != 0) return dp[N];
    dp[N] = (solve(N - 1) + solve(N - 2)) % MOD;
    return dp[N];
}

int main(){
    int N;
    cin >> N;
    cout << solve(N);
}

當你輸入題目的範例測資 10000000，會發現在編譯器這裡出現 Segmentation fault，表示記憶體區段錯誤，也就是發生了 stack overflow 的情形。但交到 Online Judge 上後，竟然 AC 了。

原因是在 Online Judge 會將記憶體上限調很高，因此就不太會觸碰到那個上限了。

這種利用遞迴實作 DP 的方式叫做 Top Down，遇到 N 太大的情形容易造成 stack overflow。Top Down 的原意是由上往下算下去，從最大問題算到最小問題，最後從最小問題求解。

Bottom up

與 Top Down 相反的就是 Bottom up，Bottom up 就是由下往上算。

Bottom up 使用到迴圈的方式做計算，從最小子問題不斷推算到最大問題。

剛才那題用 Bottom up 寫就會是這樣：

#include <iostream>

using namespace std;

const int MOD = 1000000007;

int dp[10000010] = {0};

int solve(int N){
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; ++i)
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    return dp[N];
}

int main(){
    int N;
    cin >> N;
    cout << solve(N);
}

另外這支 Bottom up 程式碼也解決了 Top Down stack overflow 的問題。

95 . [Tutorial] 別離太近

Problem Source：https://oj.ntucpc.org/problems/95

這次是編號差不能小於 $2$ ，同樣的先把 $N = 1$ 跟 $N = 2$ 的情況拿出來談：

$N = 1$ 的方法數只有 1。
$N = 2$ 的方法數為 0，因為 1 跟 2 這兩個編號差小於 2，啥都不能做。

題目也貼心地告訴你 $N = 3$ 跟 $N = 4$ 的方法數分別是 1 跟 1。

列出來比對一下發現似乎沒什麼規律： $1, 0, 1, 1$ 。

那這時候可以考慮從第 $n$ 個人去找了，那第 $n$ 個被選中外，接下來哪些也可以被選中？ $n - 2$ 、 $n - 3$ 、 $n - 4$ 這些都可以，甚至連 $1$ 也行。

這部分用數學式稍微推一下就可知道，因為編號差必定要小於 2，假設編號 n 是最後一個被選中的，且倒數第二個被選中的可以是編號 $j$ ，而 $j$ 則必須滿足不等式 $n - j \ge 2$ ，即為 $j \le n - 2$ 。

對於每個合法的 $j$ ，從 $1$ 到 $j$ 的選法恰好為 $f(j)$ ，所以最後寫成遞迴式會發現變成 $f(n - 2) + f(n - 3) + f(n - 4) + \cdots + f(1)$ ，剛好就是 $$f(n) = \sum^{n-2}_{j = 1} f(j)$$

但這有個問題，實際上寫程式會發現他的時間複雜度會是 $O(n^2)$ ，完全應付不了 $10^5$ 甚至 $10^7$ 的輸入，所以這個式子可以進一步做優化。

這邊設 $S(n) = \sum^n_{j = 1}f(j)$ ，S 函數表示的是 $f(1) + f(2) + \cdots + f(n)$ ，然後接下來你會發現 $f(n) = S(n - 2)$ 這件事。

而 $S(n) = S(n - 1) + f(n) = S(n - 1) + S(n - 2)$ ，這不就是費氏數列的長相嗎？

那這邊比較困難的是，要怎麼去理解 $S(n)$ 存在的意義是什麼？當展開 $f(n)$ 跟 $f(n - 1)$ 的時候，可以比較兩者差異： $f(n) - f(n - 1) = f(n - 2)$ ，他們兩者只差了一個 $f(n - 2)$ 。

而這個差異其實是很小的，但 $f(n)$ 又是求和的形式，所以不妨用一個變數去儲存目前總和，在計算新的 dp 值時將差異補上即可。

如果真不行的話，其實有蠻原始的方法，那就是繼續算，算到後來就會發現後面全都費氏數列。

範例程式碼（藉由輔助函數 $S(n)$ 推測出來的結果是費氏數列，因此直接寫下遞迴式）：

#include <iostream>

using namespace std;

const int MOD = 998244353;

int dp[10000010] = {0};

int solve(int N){
    dp[1] = 1, dp[2] = 0;
    for (int i = 3; i <= N; ++i){
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    }
    return dp[N];
}

int main(){
    int N;
    cin >> N;
    cout << solve(N);
}

c434. 連續正整數(Natural_Number)

Problem Source：https://zerojudge.tw/ShowProblem?problemid=c434

解題思路：

這題跟之前所有練習過的題目都不太相同，比較難去求出線性遞迴。

對於所有包含 $1$ 到 $n$ 的問題，可以將所有符合條件的集合分為兩類：

不包含 $n$ 的集合： $\{1, 2, \cdots, n - 1\}$ 中有 $f(n - 1)$ 個。
包含 $n$ 的集合則需繼續細分下去。

如果包含 $n$ ，則再根據 $n - 1$ 跟 $n - 2$ 繼續分類：

包含 $n$ 但不包含 $n - 1$ ：此時 $n$ 不能形成三個連續正整數的集合，因此為 $\{1, 2, 3, \cdots, n-2\}$ → $f(n - 2)$
包含 $n$ 跟 $n - 1$ 但不包含 $n - 2$ ：一樣， $n$ 跟 $n - 1$ 不能形成，所以是 $\{1, 2, 3, \cdots, n-3\}$ → $f(n - 3)$
包含 $n, n - 1, n - 2$ ：這時候這三個數就可以形成連續三個正整數的集合，其餘的元素 $\{1, 2, 3, \cdots, n-3\}$ 可以任意選擇（包含 or 不包含兩種情況），有這 $n - 3$ 種二元選擇，所以是 $2^{n - 3}$

所以得到遞迴式 $f(n) = f(n - 1) + f(n - 2) + f(n - 3) + 2^{n - 3}$

base case 經過推斷後可得到：

$f(1) = 0$
$f(2) = 0$ （上面兩個情況 n 都是 1 跟 2，理論上不可能形成連續三個正整數）
$f(3) = 1$ （一種情形： $\{1, 2, 3\}$ ）

範例程式碼：

因為遞迴式最後面有個指數函數，所以這部分會比較麻煩一點，如果直接寫上去的話很可能會只過一小部分測資或是 CE（浮點數不能跟整數互相運算）。

所以這邊要自己設計一個函式去做快速冪（Fast Exponentiation），把原本的指數運算 $O(n)$ 降到 $O(logn)$ 。設計函數的另外一個目的也在於讓他回傳 int （也可能是 long long）而非 double（原生函式 pow() 回傳 double）。

但在這題做快速冪會顯得有點不太好，原因是每次都要做快速冪，會有函式時間開銷，所以更好的做法是預處理，MAXN = 1000010 開一個 pow2[MAXN] 陣列來存 2 的冪次，以此在做 DP 時可以來查表。

#include <iostream>

using namespace std;

const int MOD = 1000000007;
const int MAXN = 1000010;

long long dp[MAXN] = {0};
long long pow2[MAXN];

void precompute() {
    pow2[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        pow2[i] = (pow2[i-1] * 2) % MOD; // 注意這邊也要做 MOD 模運算
    }
}

long long solve(int N){
    dp[1] = 0, dp[2] = 0, dp[3] = 1;
    for (int i = 4; i <= N; ++i){
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3] + pow2[i-3]) % MOD;
    }
    return dp[N];
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    precompute();
    
    int T;
    cin >> T;
    while (T--){
        int N;
        cin >> N;
        cout << solve(N) << "\n";
    }
}

習題練習

g555. 白色世界(簡易版)

Problem Source：https://zerojudge.tw/ShowProblem?problemid=g555

解題思路：

第 $n$ 格不染：前 $n - 1$ 要染，所以得到 $f(n - 1)$ 。
第 $n$ 格染色：第 $n - 1$ 不能染，而前 $n - 2$ 可染，所以得到了 $f(n - 2)$ 。

而這邊要注意，最後面需要再 $+ 1$ ，原因是在當第 $n$ 格染色的時候，前 $n - 2$ 也可以都不染。最後得到完整遞迴式： $f(n) = f(n - 1) + f(n - 2) + 1$

base case 為 $f(1) = 1, f(2) = 2$ 。

範例程式碼：

我發現如果每次呼叫 $f(n)$ 都要重新算一次 dp 會 TLE，所以這邊改成先算出全部的，後續根據 n 再去查表即可。

#include <iostream>

using namespace std;

const int MOD = 998244353;
const int MAXN = 200010;
long long dp[MAXN];

void precompute(){
    dp[1] = 1, dp[2] = 2;
    for (int i = 3; i <= MAXN; ++i){
        dp[i] = (dp[i - 1] + dp[i - 2] + 1) % MOD;
    }
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    precompute();
    int t;
    cin >> t;
    while (t--){
        int n;
        cin >> n;
        cout << dp[n] << "\n";
    }
}

Dice Combinations

Problem Source：https://cses.fi/problemset/task/1633

題目翻譯：

你的任務是計算透過擲骰子一次或多次來建構和為 $n$ 的數列的方法數。每次擲骰子的結果介於 $1$ 和 $6$ 之間。

舉例來說，如果 $n = 3$ ，則有四種方法：

1 + 1 + 1
1 + 2
2 + 1
3

解題思路：

假設 $i$ 是擲骰子的點數，如果在最後一次擲出 $i$ 點，則前面所有擲骰的和必須為 $n - i$ 。

Why？像 $n = 3$ 的其中一個方法， $1 + 1 + 1$ 裡面三個 1 都是擲出來的點數，如果最後一個是 1，則前面的和必須為 3 - 1 = 2，剛好也呼應了。

所以這邊來列遞迴式囉：

最後擲出 1 點 → $f(n - 1)$
最後擲出 2 點 → $f(n - 2)$
…
最後擲出 6 點 → $f(n - 6)$

完整遞迴式： $f(n - 1) + f(n - 2) + f(n - 3) + f(n - 4) + f(n - 5) + f(n - 6)$

另外 base case 為 n = 0，f(0) = 1 的情況。

範例程式碼：

#include <iostream>

using namespace std;

const int MOD = 1000000007;

int main(){
    int n;
    cin >> n;
    long long dp[n + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; ++i){
        dp[i] = 0;
        for (int dice = 1; dice <= 6; ++dice){
            if (i - dice >= 0){
                dp[i] = (dp[i] + dp[i - dice]) % MOD;
            }
        }
    }
    cout << dp[n];
}

可以進一步用滑動窗口（Sliding Window）的方式優化空間複雜度至 $O(1)$ ：

#include <iostream>
using namespace std;

const int MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    
    // 只保存最近 7 個值（dp[i-6] 到 dp[i]）
    long long dp[7] = {1, 0, 0, 0, 0, 0, 0}; // dp[0] = 1
    
    for (int i = 1; i <= n; i++) {
        long long sum = 0;
        // 加總前 6 個值
        for (int j = 1; j <= 6; j++) {
            if (i - j >= 0) {
                sum = (sum + dp[(i - j) % 7]) % MOD;
            }
        }
        dp[i % 7] = sum;
    }
    
    cout << dp[n % 7] << endl;
    
    return 0;
}