Introduction to DP

ITừ đệ quy đến bảng

Dãy Fibonacci có $F_0 = 0$, $F_1 = 1$ và $F_n = F_{n-1} + F_{n-2}$. Viết đúng như định nghĩa:

ll fib(ll n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

Gọi $C_n$ là số lệnh gọi hàm (kể cả lệnh gọi đầu tiên) khi tính fib(n). Ta có $C_0 = C_1 = 1$ và $C_n = C_{n-1} + C_{n-2} + 1$, từ đó chứng minh được $C_n = 2F_{n+1} - 1$ (thử với vài $n$ nhỏ để thấy). Vì cứ mỗi bước $F_n$ gấp lên khoảng 1,618 lần nên $C_{40} \approx 3{,}3 \cdot 10^8$ và $C_{50} \approx 4{,}1 \cdot 10^{10}$, trong khi chỉ có $n + 1$ giá trị $F_0, \dots, F_n$ khác nhau.

Nguyên nhân thấy rõ trên hình: fib(3) luôn trả về cùng một giá trị dù được gọi từ đâu, vì kết quả của một bài toán con chỉ phụ thuộc vào đối số. Vậy lần đầu tính xong ta cất kết quả đi, các lần sau lấy ra. Có hai cách cài.

Đệ quy có nhớ (memoization) giữ nguyên hàm trên, thêm một bảng memo ghi giá trị đã biết; trước khi gọi, mọi ô được gán $-1$, nghĩa là chưa tính:

ll memo[100];

ll fib(ll n) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Thân hàm của mỗi fib(k) chạy nhiều nhất một lần và tốn $O(1)$ ngoài các lệnh gọi con, nên cả bài là $O(n)$. Đây là quy tắc đếm dùng suốt bài: thời gian xấp xỉ số trạng thái nhân chi phí chuyển của mỗi trạng thái.

Lập bảng (bottom-up) bỏ hẳn đệ quy: tính $F_0, F_1, F_2, \dots$ theo thứ tự tăng, mỗi ô chỉ dùng các ô đã có.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n, f[100];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    f[1] = 1;
    for (ll i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
    cout << f[n] << '\n';
}

ChạyInput50

Output12586269025

$F_{92}$ là số Fibonacci lớn nhất còn vừa long long; $F_{93}$ đã vượt $9 \cdot 10^{18}$. Vòng lặp chỉ nhìn hai ô liền trước nên bộ nhớ có thể rút xuống hai biến.

Đệ quy có nhớ viết thẳng từ công thức và chỉ chạm tới những trạng thái thật sự cần, nhưng tốn chi phí gọi hàm và độ sâu đệ quy (hàng triệu tầng dễ tràn ngăn xếp). Lập bảng nhanh hơn và dễ nén bộ nhớ, đổi lại ta phải tự xác định thứ tự tính. Các mục sau dùng bảng; đệ quy có nhớ là phương án dự phòng khi thứ tự tính khó nhìn ra.

Ví dụBậc Đá Tối Ưu

Đề. Có $N \le 10^5$ bậc đá, bậc $i$ cao $h_i$. Robot đứng ở bậc 1, mỗi lần nhảy sang bậc $i + 1$ hoặc $i + 2$, tốn $|h_i - h_j|$. In tổng chi phí nhỏ nhất để tới bậc $N$.

Lời giải. Gọi $\mathrm{dp}_i$ là chi phí nhỏ nhất để tới bậc $i$. Bước nhảy cuối cùng tới $i$ đến từ bậc $i - 1$ hoặc $i - 2$, nên $\mathrm{dp}_i = \min(\mathrm{dp}_{i-1} + |h_i - h_{i-1}|,\ \mathrm{dp}_{i-2} + |h_i - h_{i-2}|)$, với $\mathrm{dp}_1 = 0$ và $\mathrm{dp}_2 = |h_2 - h_1|$. Giống hệt Fibonacci, chỉ thay cộng bằng lấy min. Vét cạn mọi đường nhảy là $F_N$ đường; bảng chỉ có $N$ ô, mỗi ô $O(1)$. Với ví dụ, $\mathrm{dp} = (0, 5, 4, 7, 7)$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5;
ll n, h[N], dp[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> h[i];
    dp[2] = abs(h[2] - h[1]);
    for (ll i = 3; i <= n; i++)
        dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
    cout << dp[n] << '\n';
}

ChạyInput5
8 13 4 10 7

Output7

IITrạng thái và công thức

Fibonacci cho sẵn công thức. Ở đa số bài, phần khó nhất là tự tìm ra nó. Một lời giải quy hoạch động luôn trả lời đủ bốn câu:

1. Trạng thái. Bài toán con được mô tả bởi những tham số nào, và dp[...] nghĩa chính xác là gì (đếm gì, tối ưu gì, với điều kiện gì)?
2. Công thức chuyển. dp của một trạng thái tính từ dp của những trạng thái nào? Cách tìm: xét lựa chọn cuối cùng (phần tử cuối, bước cuối, vật cuối) rồi hỏi phần còn lại là bài toán con nào.
3. Giá trị cơ sở. Trạng thái nhỏ nhất nào có đáp án biết sẵn?
4. Thứ tự tính và đáp án. Thứ tự nào bảo đảm khi cần một ô thì mọi ô nó phụ thuộc đã có, và đáp án nằm ở ô nào?

Công thức chuyển chỉ đúng khi có hai tính chất. Thứ nhất là tối ưu con: phần còn lại của một phương án tối ưu cũng phải tối ưu cho bài con của nó, vì nếu không ta thay bằng phương án tốt hơn thì cả phương án lớn cũng tốt hơn. Với bài đếm, tính chất này đổi thành: các trường hợp (ví dụ “phần tử cuối là gì”) phải rời nhau và phủ hết mọi cấu hình, để mỗi cấu hình được đếm đúng một lần. Thứ hai là trạng thái đủ thông tin: khi đã biết dp của trạng thái, các quyết định về sau không cần biết ta tới đó bằng đường nào. Tính chất thứ hai dễ bị bỏ quên nhất.

Dãy con tăng dài nhất (longest increasing subsequence, LIS). Cho dãy $a_1, \dots, a_n$. Dãy con là dãy thu được bằng cách xóa một số phần tử và giữ nguyên thứ tự những phần tử còn lại. Tìm độ dài lớn nhất của một dãy con tăng nghiêm ngặt. Có $2^n$ dãy con nên vét cạn không đi xa được.

Trạng thái: $\mathrm{dp}_i$ là độ dài dãy con tăng dài nhất kết thúc đúng tại $a_i$. Phần tử cuối nằm trong định nghĩa vì chỉ biết nó ta mới biết có nối thêm được $a_i$ hay không. Công thức chuyển: xét phần tử đứng ngay trước $a_i$ trong dãy tối ưu. Nếu không có thì dãy chỉ gồm $a_i$, độ dài 1. Nếu đó là $a_j$ với $j < i$ và $a_j < a_i$ thì phần còn lại là một dãy tăng kết thúc tại $a_j$, và dài nhất có thể là $\mathrm{dp}_j$:

Ký hiệu $\max$ có điều kiện viết bên dưới nghĩa là lấy số lớn nhất trong các giá trị thỏa điều kiện đó: ở đây là $\mathrm{dp}_j$ lớn nhất trong các $j < i$ có $a_j < a_i$, và số 0 lo trường hợp không có $j$ nào. $\min$ viết kiểu này cũng đọc tương tự.

Vì sao chỉ cần $\mathrm{dp}_j$? Nếu phần đứng trước $a_i$ kết thúc ở $a_j$ mà chưa phải dãy dài nhất kết thúc ở $a_j$, thay nó bằng dãy dài nhất ấy vẫn cho một dãy tăng hợp lệ (điều kiện nối $a_j < a_i$ không đổi) mà dài hơn: mâu thuẫn. Thứ tự tính là $i$ tăng dần, đáp án là số lớn nhất trong các $\mathrm{dp}_i$. Với $a = (5, 2, 8, 6, 3, 6, 9, 7)$ ta được $\mathrm{dp} = (1, 1, 2, 2, 2, 3, 4, 4)$, đáp án 4.

Mảng par[i] ghi phần tử đứng trước $a_i$ trong dãy tốt nhất. Đi ngược từ ô tốt nhất theo par rồi đảo lại ta in được chính dãy con. Đó là truy vết (reconstruction), dùng lại nhiều lần ở các mục sau.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 5005;
ll n, a[N], dp[N], par[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    ll best = 1;
    for (ll i = 1; i <= n; i++) {
        dp[i] = 1;
        for (ll j = 1; j < i; j++)
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                par[i] = j;
            }
        if (dp[i] > dp[best]) best = i;
    }
    vector<ll> seq;
    for (ll i = best; i; i = par[i]) seq.push_back(a[i]);
    reverse(seq.begin(), seq.end());
    cout << dp[best] << '\n';
    for (ll x : seq) cout << x << ' ';
    cout << '\n';
}

ChạyInput8
5 2 8 6 3 6 9 7

Output4
2 3 6 9

Thời gian là $O(n^2)$: với $n = 5000$ có khoảng $1{,}25 \cdot 10^7$ cặp $(j, i)$, thoải mái; với $n = 2 \cdot 10^5$ thì không, và khi đó ta tính nhanh hơn bằng chặt nhị phân (bài 0.6) hoặc cây Fenwick (bài 1.7). Code trên theo kiểu kéo: mỗi $i$ nhìn lại các $j$ đứng trước. Có thể viết kiểu đẩy: khi $\mathrm{dp}_j$ đã xong thì cập nhật cho mọi $i > j$ nối được. Hai kiểu tính cùng một công thức, chọn kiểu nào cho vòng lặp gọn hơn.

Ví dụLịch Hoạt Động

Đề. Kế hoạch $N \le 10^5$ ngày; mỗi ngày chọn đúng một trong ba hoạt động $A, B, C$, nhận $a_i, b_i, c_i$ điểm, và không được chọn cùng một hoạt động hai ngày liền. In tổng điểm lớn nhất.

Lời giải. Thử đặt $\mathrm{dp}_i$ là tổng điểm lớn nhất sau $i$ ngày thì hỏng đúng như câu hỏi trên: muốn biết hôm nay chọn được hoạt động nào, phải biết hôm qua đã chọn gì. Đưa thông tin đó vào trạng thái: $\mathrm{dp}_{i,j}$ là tổng điểm lớn nhất sau $i$ ngày với ngày $i$ chọn hoạt động $j$. Hôm qua là một trong hai hoạt động khác $j$, nên $\mathrm{dp}_{i,j} = s_{i,j} + \max_{k \ne j} \mathrm{dp}_{i-1,k}$, với $\mathrm{dp}_{0,\cdot} = 0$. Đáp án là số lớn nhất trong ba ô $\mathrm{dp}_{N,j}$. Trạng thái chỉ thêm đúng phần thiếu: một trong ba giá trị, nên bảng $3N$ ô.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5;
ll n, a[N][3], dp[N][3];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++)
        for (ll j = 0; j < 3; j++) cin >> a[i][j];
    for (ll i = 1; i <= n; i++)
        for (ll j = 0; j < 3; j++)
            for (ll k = 0; k < 3; k++)
                if (k != j) dp[i][j] = max(dp[i][j], dp[i - 1][k] + a[i][j]);
    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << '\n';
}

ChạyInput4
8 3 5
6 9 4
7 2 10
5 11 6

Output38

IIIQuy hoạch động trên đoạn

Có bài mà bài con tự nhiên là một đoạn liên tục $[l, r]$ của dãy: lời giải của đoạn dài ghép từ lời giải của hai đoạn ngắn hơn, nối nhau ở một điểm tách $k$.

Ví dụ: một thanh gỗ dài $L$ đã đánh dấu $m$ vị trí cần cắt, $0 < p_1 < p_2 < \dots < p_m < L$. Mỗi nhát cắt một mảnh gỗ dài $\ell$ tốn $\ell$. Phải cắt tại mọi vị trí đánh dấu theo thứ tự tùy ý; tìm tổng chi phí nhỏ nhất. Thứ tự có ảnh hưởng: thanh dài 10 đánh dấu ở 2, 4, 7. Cắt ở 2 trước thì tốn $10 + 8 + 6 = 24$, cắt ở 7 trước tốn $10 + 7 + 4 = 21$, cắt ở 4 trước tốn $10 + 4 + 6 = 20$. Có $m!$ thứ tự nên không thể thử hết.

Ta nhìn vào nhát cắt đầu tiên trên một mảnh. Nó cắt tại một vị trí $p_k$ nào đó và tốn đúng chiều dài mảnh; sau nhát này hai nửa tách rời hẳn và được cắt xong một cách độc lập. Đặt $p_0 = 0$, $p_{m+1} = L$ và gọi $\mathrm{dp}_{i,j}$ là chi phí nhỏ nhất để cắt xong mảnh từ $p_i$ tới $p_j$:

Đáp án là $\mathrm{dp}_{0,m+1}$. Hai bài con ở vế phải đều là đoạn ngắn hơn, nên thứ tự tính phải theo độ dài $j - i$ tăng dần. Với $p = (0, 2, 4, 7, 10)$: $\mathrm{dp}_{0,2} = 4$, $\mathrm{dp}_{1,3} = 5$, $\mathrm{dp}_{2,4} = 6$; rồi $\mathrm{dp}_{0,3} = 7 + \min(5, 4) = 11$, $\mathrm{dp}_{1,4} = 8 + \min(6, 5) = 13$; cuối cùng $\mathrm{dp}_{0,4} = 10 + \min(13, 10, 11) = 20$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll L, m, p[505], dp[505][505];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> L >> m;
    for (ll i = 1; i <= m; i++) cin >> p[i];
    p[m + 1] = L;
    for (ll len = 2; len <= m + 1; len++)
        for (ll i = 0; i + len <= m + 1; i++) {
            ll j = i + len;
            dp[i][j] = 1e18;
            for (ll k = i + 1; k < j; k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            dp[i][j] += p[j] - p[i];
        }
    cout << dp[0][m + 1] << '\n';
}

ChạyInput10 3
2 4 7

Output20

Có $O(m^2)$ trạng thái, mỗi trạng thái thử $O(m)$ điểm tách, tổng $O(m^3)$. Số phép tính thật là khoảng $m^3 / 6$ (số bộ ba $i < k < j$), nên $m = 500$ tốn cỡ $2 \cdot 10^7$ còn $m = 5000$ thì không chạy nổi. Bài 4.2 sẽ cho thấy khi nào hạ được $O(m^3)$ xuống $O(m^2)$.

Ví dụGộp Các Khối Kề Nhau

Đề. Có $N \le 400$ khối thành hàng, khối $i$ cỡ $A_i \le 10^9$. Mỗi thao tác gộp hai khối kề nhau cỡ $x$, $y$ thành một khối cỡ $x + y$, tốn $x + y$. In tổng chi phí nhỏ nhất để còn một khối.

Lời giải. Lần ghép cuối cùng gộp một khối tạo từ đoạn $[l, k]$ với một khối tạo từ đoạn $[k + 1, r]$, và tốn đúng tổng cả đoạn, bất kể trước đó gộp ra sao. Hai nửa được gộp độc lập. Vậy $\mathrm{dp}_{l,r}$, chi phí nhỏ nhất để gộp đoạn khối $[l, r]$ thành một khối, bằng $\min_{l \le k < r}(\mathrm{dp}_{l,k} + \mathrm{dp}_{k+1,r}) + (S_r - S_{l-1})$, với $S$ là tổng tiền tố và $\mathrm{dp}_{l,l} = 0$. Ở đây đoạn là đoạn khối đóng $[l, r]$ chứ không phải đoạn giữa hai vị trí cắt như thanh gỗ, nên điểm tách chạy từ $l$ tới $r - 1$. Với ví dụ $(2, 2, 1, 2)$: tách giữa $[1, 2]$ và $[3, 4]$ cho $4 + 3 + 7 = 14$. Thời gian cỡ $400^3/6 \approx 10^7$; chi phí tới cỡ $10^{14}$ nên dùng ll.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n, s[405], dp[405][405];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    for (ll len = 2; len <= n; len++)
        for (ll l = 1; l + len - 1 <= n; l++) {
            ll r = l + len - 1;
            dp[l][r] = 1e18;
            for (ll k = l; k < r; k++) dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
            dp[l][r] += s[r] - s[l - 1];
        }
    cout << dp[1][n] << '\n';
}

ChạyInput4
2 2 1 2

Output14