Dynamic Programming

Từ đệ 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

Trạ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 05) hoặc cây Fenwick (bài 16). 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

Đổi tiền

Có các mệnh giá $c_1, \dots, c_k$, mỗi mệnh giá dùng bao nhiêu đồng cũng được. Tạo tổng đúng bằng $x$ bằng ít đồng nhất.

Cách nghĩ đầu tiên là tham lam (bài 04): luôn lấy đồng lớn nhất không vượt phần còn lại. Với các mệnh giá $\{1, 3, 4\}$ và $x = 6$, tham lam lấy $4 + 1 + 1$ (3 đồng), trong khi $3 + 3$ chỉ cần 2 đồng. Lấy đồng lớn trước có thể phá hỏng phần còn lại, nên ta phải xét mọi khả năng một cách có hệ thống.

Trạng thái: $\mathrm{dp}_s$ là số đồng ít nhất để tạo tổng đúng $s$, bằng $+\infty$ nếu không tạo được. Công thức chuyển: trong một phương án tối ưu cho $s$, lấy ra một đồng bất kỳ, mệnh giá $c$. Phần còn lại tạo tổng $s - c$ và (tối ưu con) phải dùng ít đồng nhất có thể. Ta chưa biết $c$ là mệnh giá nào nên thử tất cả:

Số hạng nào bằng $+\infty$ thì bỏ qua. Duyệt $s$ tăng dần vì $\mathrm{dp}_s$ phụ thuộc các ô nhỏ hơn. Với $\{1, 3, 4\}$ ta có $\mathrm{dp}_{0..6} = (0, 1, 2, 1, 1, 2, 2)$; riêng $\mathrm{dp}_6 = 1 + \min(\mathrm{dp}_5, \mathrm{dp}_3, \mathrm{dp}_2) = 2$, đạt khi lấy đồng 3 ở bước cuối.

Đổi câu hỏi thành đếm số cách thì trước hết phải nói rõ hai cách khác nhau khi nào. Hai cách hiểu cho hai bài toán, và hai đoạn code chỉ khác nhau ở thứ tự của hai vòng for.

Nếu $1 + 2$ và $2 + 1$ là hai cách (dãy có thứ tự), mỗi dãy có đúng một phần tử cuối $c$, bỏ nó đi còn một dãy tạo tổng $s - c$. Vậy $\mathrm{dp}_s = \sum_{c_i \le s} \mathrm{dp}_{s - c_i}$, tức tổng các $\mathrm{dp}_{s - c_i}$ qua mọi mệnh giá $c_i \le s$ (ký hiệu $\sum$ là phép cộng, điều kiện viết bên dưới cho biết cộng những số nào), với $\mathrm{dp}_0 = 1$ (dãy rỗng). Tổng $s$ nằm ở vòng ngoài, mệnh giá ở vòng trong.

Nếu chỉ quan tâm mỗi mệnh giá dùng bao nhiêu đồng (tập mệnh giá), ta xử lý lần lượt từng mệnh giá để mỗi tập chỉ được sinh một lần. Gọi $\mathrm{dp}_{k,s}$ là số cách tạo $s$ chỉ dùng $k$ mệnh giá đầu. Hoặc không dùng mệnh giá $c_k$, còn $\mathrm{dp}_{k-1,s}$ cách; hoặc dùng ít nhất một đồng $c_k$, bỏ một đồng ấy đi thì còn $\mathrm{dp}_{k,s-c_k}$ cách, và ở đó $c_k$ vẫn được dùng tiếp:

Nén thành một mảng, mệnh giá ở vòng ngoài và $s$ tăng dần ở vòng trong: dp[s] += dp[s - c]. Duyệt tăng chính là để dp[s - c] đã chứa các cách dùng $c$. Chương trình dưới in số dãy có thứ tự (f) rồi số tập mệnh giá (g).

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

const ll MOD = 1e9 + 7, N = 1e6 + 5;
ll n, x, c[105], f[N], g[N];

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

    cin >> n >> x;
    for (ll i = 0; i < n; i++) cin >> c[i];
    f[0] = g[0] = 1;
    for (ll s = 1; s <= x; s++)
        for (ll i = 0; i < n; i++)
            if (c[i] <= s) f[s] = (f[s] + f[s - c[i]]) % MOD;
    for (ll i = 0; i < n; i++)
        for (ll s = c[i]; s <= x; s++) g[s] = (g[s] + g[s - c[i]]) % MOD;
    cout << f[x] << '\n' << g[x] << '\n';
}

ChạyInput2 5
1 2

Output8
3

Với $x = 5$ và hai mệnh giá 1, 2: có 3 tập ($2+2+1$, $2+1+1+1$, năm đồng 1) nhưng 8 dãy có thứ tự, vì ba tập đó cho lần lượt 3, 4 và 1 cách xếp. Đổi chỗ hai vòng for là đổi sang bài toán khác, nên phải đọc kỹ đề xem “cách” có phân biệt thứ tự không.

Ba lô 0/1

Khi mỗi vật chỉ lấy được một lần, ta có bài toán ba lô 0/1 (knapsack). Có $n$ vật, vật $i$ nặng $w_i$ và có giá trị $v_i$. Chọn một tập vật có tổng trọng lượng không quá sức chứa $C$ sao cho tổng giá trị lớn nhất. Vét cạn $2^n$ tập thì với $n = 100$ là vô vọng.

Mỗi vật có hai khả năng, lấy hoặc không lấy, và có lấy được hay không còn tùy sức chứa còn lại. Vậy trạng thái cần hai tham số: $\mathrm{dp}_{i,c}$ là tổng giá trị lớn nhất khi chỉ xét $i$ vật đầu và tổng trọng lượng không quá $c$. Xét vật $i$: không lấy thì còn $\mathrm{dp}_{i-1,c}$; lấy (nếu $w_i \le c$) thì phần còn lại là $i - 1$ vật đầu với sức chứa $c - w_i$.

Đáp án là $\mathrm{dp}_{n,C}$. Bảng có $(n + 1)(C + 1)$ ô, mỗi ô $O(1)$, tổng thời gian $O(nC)$.

Hình dùng bốn vật $(w, v) = (3, 4), (2, 3), (4, 6), (1, 1)$ và $C = 6$. Ô cuối $\mathrm{dp}_{4,6} = \mathrm{dp}_{3,6}$ vì lấy thêm vật 4 chỉ được $\mathrm{dp}_{3,5} + 1 = 8$, kém 9. Ô $\mathrm{dp}_{3,6} = \mathrm{dp}_{2,2} + 6 = 9$ (lấy vật 3) và $\mathrm{dp}_{2,2} = \mathrm{dp}_{1,0} + 3$ (lấy vật 2). Đường truy ngược cho tập $\{2, 3\}$, nặng 6 và giá trị 9.

Điều kiện “không quá $c$” ứng với khởi tạo $\mathrm{dp}_{0,c} = 0$ cho mọi $c$. Nếu đề đòi trọng lượng đúng bằng $c$, chỉ $\mathrm{dp}_{0,0} = 0$ còn các ô khác khởi tạo $-\infty$ (hoặc $+\infty$ khi tối thiểu hóa).

Hàng $i$ chỉ dùng hàng $i - 1$ nên ta giữ một mảng dp[c] và sửa tại chỗ: dp[c] = max(dp[c], dp[c - w] + v). Công thức cần dp[c - w] của hàng cũ, tức khi chưa xét vật $i$. Vì $c - w < c$, nếu duyệt $c$ giảm dần thì ô $c - w$ chưa bị sửa trong lượt này. Duyệt tăng dần thì dp[c - w] đã chứa vật $i$ và vật bị lấy lại nhiều lần; đó chính là ba lô không giới hạn số lần, tức bài đổi tiền ở mục trước. Hướng duyệt quyết định bài toán. Với một vật $w = 2$, $v = 3$ và $C = 4$: duyệt giảm cho $\mathrm{dp} = (0, 0, 3, 3, 3)$, duyệt tăng cho $(0, 0, 3, 3, 6)$ vì vật được lấy hai lần.

for (ll i = 1; i <= n; i++)
    for (ll c = C; c >= w[i]; c--) dp[c] = max(dp[c], dp[c - w[i]] + v[i]);

Bộ nhớ giảm từ $O(nC)$ xuống $O(C)$. Với $n = 1000$ và $C = 10^5$, bảng đầy đủ có $10^8$ ô, tức 400 MB với int, còn mảng một chiều chỉ 400 KB. Mảng nhỏ còn nằm gọn trong bộ nhớ đệm của CPU, nên chạy nhanh hơn hẳn:

Cùng $10^7$ trạng thái, một mảng duyệt giảm nhanh gấp khoảng 7 lần bảng hai chiều và hơn 20 lần đệ quy có nhớ. Không cần truy vết thì hãy nén.

Bảng hai chiều, truy vết

Khi trạng thái là một ô $(i, j)$ của bảng, công thức chuyển thường lấy từ các ô kề đã tính. Xét bảng $R \times C$ số nguyên (có thể âm). Đi từ ô $(1, 1)$ tới ô $(R, C)$, mỗi bước sang phải hoặc xuống dưới. Tìm đường có tổng các ô đi qua lớn nhất và in đường đó. Số đường là $\binom{R + C - 2}{R - 1}$, quá nhiều để duyệt.

Trạng thái: $\mathrm{dp}_{i,j}$ là tổng lớn nhất của một đường từ $(1, 1)$ tới $(i, j)$. Bước cuối tới $(i, j)$ đến từ ô trên hoặc ô trái:

Duyệt hàng từ trên xuống, mỗi hàng từ trái sang phải: khi tới $(i, j)$ cả hai ô nguồn đã có. Các ô ngoài bảng (hàng 0, cột 0) phải là $-\infty$, không phải 0. Nếu đặt 0 thì một đường “xuất phát từ ngoài bảng” sẽ thắng mỗi khi mọi đường thật có tổng âm.

Muốn in đường, ta đi ngược từ $(R, C)$. Tại ô $(i, j)$ chọn ô nguồn có $\mathrm{dp}$ lớn hơn, vì đó chính là ô đã cho ra $\mathrm{dp}_{i,j}$; ghi lại bước vừa lùi và dừng khi tới $(1, 1)$, rồi đảo chuỗi bước. Không cần mảng mũi tên riêng, vì bảng dp đã chứa đủ thông tin để suy ra mọi lựa chọn.

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

ll R, C, a[105][105], dp[105][105];

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

    cin >> R >> C;
    for (ll i = 1; i <= R; i++)
        for (ll j = 1; j <= C; j++) cin >> a[i][j];
    for (ll i = 0; i <= R; i++)
        for (ll j = 0; j <= C; j++) dp[i][j] = -1e18;
    for (ll i = 1; i <= R; i++)
        for (ll j = 1; j <= C; j++) {
            if (i == 1 && j == 1) dp[i][j] = a[i][j];
            else dp[i][j] = a[i][j] + max(dp[i - 1][j], dp[i][j - 1]);
        }
    string path;
    ll i = R, j = C;
    while (i > 1 || j > 1) {
        if (dp[i - 1][j] >= dp[i][j - 1]) {
            path += 'D';
            i--;
        } else {
            path += 'R';
            j--;
        }
    }
    reverse(path.begin(), path.end());
    cout << dp[R][C] << '\n' << path << '\n';
}

ChạyInput3 4
2 -3 4 1
-1 5 -2 3
3 -4 6 -1

Output9
DRRDR

Đường tối ưu đi xuống, phải, phải, xuống, phải: $2 - 1 + 5 - 2 + 6 - 1 = 9$. Cái giá của truy vết là phải giữ cả bảng; nén thành một hàng như ở ba lô thì mất đường đi. Cùng khuôn này, thay max bằng phép cộng và ô cấm bằng 0 ta đếm được số đường; thay hai chiều của bảng bằng hai chuỗi ta được ví dụ dưới.

Ví dụChuỗi Chung Dài Nhất

Đề. Cho hai chuỗi chữ thường $s$, $t$, mỗi chuỗi dài tối đa 3000. In một dãy con chung dài nhất (bất kỳ nếu có nhiều); độ dài 0 thì in dòng rỗng.

Lời giải. Trạng thái là một cặp tiền tố: $\mathrm{dp}_{i,j}$ là độ dài dãy con chung dài nhất của $i$ ký tự đầu của $s$ và $j$ ký tự đầu của $t$. Ô $(i, j)$ chỉ cần xét hai ký tự cuối:

với hàng 0 và cột 0 bằng 0. Khi $s_i \ne t_j$, một dãy con chung không thể dùng cả hai ký tự ấy (nếu dùng thì cả hai là ký tự cuối của dãy, nên bằng nhau), nên phải bỏ một trong hai. Khi $s_i = t_j$, ghép hai ký tự ấy với nhau không bao giờ thiệt: nếu dãy tối ưu chỉ dùng một trong hai, đổi cách ghép ký tự cuối sang đúng cặp $(i, j)$ vẫn được dãy cùng độ dài.

Truy vết từ ô $(n, m)$: ký tự bằng nhau thì ghi lại và đi chéo, khác thì đi tới ô kề có giá trị lớn hơn. Mỗi lần ghi, $\mathrm{dp}$ giảm đúng 1, nên ghi được đúng $\mathrm{dp}_{n,m}$ ký tự; đảo lại là xong. Bảng có $9 \cdot 10^6$ ô; dùng int thì khoảng 36 MB, và phải giữ cả bảng để truy vết. Chuỗi đánh số từ 0 (s[i - 1]) nhưng bảng đánh số từ 1, vì $i$ là độ dài tiền tố.

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

string s, t;
int dp[3005][3005];

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

    cin >> s >> t;
    ll n = s.size(), m = t.size();
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    string ans;
    ll i = n, j = m;
    while (i > 0 && j > 0) {
        if (s[i - 1] == t[j - 1]) {
            ans += s[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
        else j--;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
}

ChạyInputabcde
ace

Outputace

Quy 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 41 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

Chọn trạng thái

Phần lớn thời gian của một bài quy hoạch động nằm ở việc chọn trạng thái. Vài nguyên tắc giúp chọn nhanh hơn.

Đếm trước khi code. Thời gian xấp xỉ số trạng thái nhân chi phí chuyển. Giới hạn của đề cho biết cỡ nào còn chạy được: $n$ từ $10^5$ đến $10^6$ cho phép trạng thái một chiều với chuyển $O(1)$ hoặc $O(\log n)$; $n \le 5000$ cho bảng $n^2$ với chuyển $O(1)$; $n \le 500$ cho $n^3$ như quy hoạch động trên đoạn; hai tham số nhỏ, ví dụ $n \le 100$ và tổng giá trị $\le 10^5$, cho ba lô. Một trạng thái đúng nhưng cần $10^{10}$ phép thì phải đổi trạng thái, tối ưu code không cứu được.

Thiếu thông tin thì thêm vào trạng thái, và chỉ thêm đúng phần thiếu. Đếm xâu nhị phân độ dài $n$ không có hai số 1 liền nhau: muốn biết được thêm bit 1 hay không phải biết bit cuối, nên trạng thái là $(i, b)$ với $b$ là bit cuối. Thêm 0 thì sau bit nào cũng được, thêm 1 chỉ sau bit 0: $\mathrm{dp}_{i,0} = \mathrm{dp}_{i-1,0} + \mathrm{dp}_{i-1,1}$ và $\mathrm{dp}_{i,1} = \mathrm{dp}_{i-1,0}$. Với $n = 3$ có $3 + 2 = 5$ xâu: 000, 001, 010, 100, 101.

Giới hạn lớn thì đổi vai. Nếu một chiều của bảng quá lớn mà một đại lượng khác lại nhỏ, thử đưa đại lượng nhỏ vào trạng thái và dùng đại lượng lớn làm giá trị cần tối ưu. Ví dụ dưới làm đúng như vậy với ba lô.

Chuyển nhiều thì dùng tiền tố hoặc cấu trúc dữ liệu. Nếu $\mathrm{dp}_s$ là tổng (hoặc min, max) của một dãy ô liên tiếp ở hàng trước, ta tính nhanh bằng tổng tiền tố (bài 02) hay cấu trúc dữ liệu (bài 16, 17), hạ chi phí chuyển từ $O(n)$ xuống $O(1)$ hoặc $O(\log n)$. Chẳng hạn truy vấn “$\max \mathrm{dp}_j$ trên mọi $j$ có $a_j < a_i$” của LIS được cây Fenwick trả lời trong $O(\log n)$, nên cả bài còn $O(n \log n)$.

Modulo và kiểu dữ liệu. Bài đếm thường đòi kết quả theo modulo $10^9 + 7$: lấy dư sau mỗi phép cộng, với phép trừ thì cộng thêm modulo trước khi lấy dư để khỏi âm. Bài tối ưu tràn int rất nhanh (tổng $10^5$ số cỡ $10^9$ đã tới $10^{14}$): chọn long long từ đầu, và chọn giá trị vô cực đủ lớn nhưng cộng thêm không tràn.

Kiểm tra. Hầu hết lời giải sai nằm ở định nghĩa trạng thái hoặc công thức, hiếm khi ở cú pháp. Viết bản vét cạn cho $n$ nhỏ (bài 00) và so với bản quy hoạch động trên nhiều test ngẫu nhiên; khi lệch, in bảng dp của một test cỡ 5 rồi tính tay vài ô.

Ví dụBa Lô Theo Tổng Giá Trị

Đề. Có $N \le 100$ vật, vật $i$ nặng $W_i$ và có giá trị $V_i \le 1000$; ba lô chịu tổng trọng lượng $C \le 10^9$. Chọn một tập vật, mỗi vật tối đa một lần, có tổng trọng lượng không quá $C$ để tổng giá trị lớn nhất.

Lời giải. Bảng ba lô theo trọng lượng cần $10^9$ ô, không khả thi. Nhưng tổng mọi giá trị $S = V_1 + \dots + V_N \le 10^5$ lại nhỏ, nên đổi vai: $\mathrm{dp}_x$ là tổng trọng lượng nhỏ nhất của một tập có tổng giá trị đúng $x$, với $\mathrm{dp}_0 = 0$ và các ô khác $+\infty$. Mỗi vật $(w, v)$ sửa mảng với $x$ giảm dần: $\mathrm{dp}_x \leftarrow \min(\mathrm{dp}_x, \mathrm{dp}_{x-v} + w)$. Đáp án là $x$ lớn nhất có $\mathrm{dp}_x \le C$, và $x = 0$ luôn thỏa. Giữ trọng lượng nhỏ nhất cho mỗi giá trị là đủ, vì ràng buộc chỉ là tổng trọng lượng không quá $C$: tập nhẹ hơn cùng giá trị luôn thay được tập nặng hơn.

Thời gian $O(N \cdot S) = 10^7$, bộ nhớ $O(S)$. Trọng lượng cộng lại tới $10^{11}$ nên dùng ll, vô cực đặt $10^{18}$ để cộng thêm một trọng lượng vẫn không tràn. Với ví dụ, vật 1 và 2 cho giá trị 13, nặng đúng 10; mọi giá trị lớn hơn đều cần từ 11 trở lên.

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

ll n, C, w[105], v[105], dp[100005];

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

    cin >> n >> C;
    ll S = 0;
    for (ll i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
        S += v[i];
    }
    for (ll x = 1; x <= S; x++) dp[x] = 1e18;
    for (ll i = 0; i < n; i++)
        for (ll x = S; x >= v[i]; x--) dp[x] = min(dp[x], dp[x - v[i]] + w[i]);
    ll ans = 0;
    for (ll x = 0; x <= S; x++)
        if (dp[x] <= C) ans = x;
    cout << ans << '\n';
}

ChạyInput4 10
6 8
4 5
5 7
3 4

Output13