DP on Sequences

IĐoạn con tổng lớn nhất

Cho dãy $a_1, \dots, a_n$ gồm các số nguyên có thể âm. Tìm đoạn con (các phần tử liên tiếp, khác dãy con ở chỗ không được bỏ phần tử giữa chừng) không rỗng có tổng lớn nhất. Thử mọi cặp đầu cuối rồi tính tổng bằng tổng tiền tố (bài 0.3) mất $O(n^2)$. Cũng đã biết cách làm $O(n)$: với mỗi vị trí cuối $r$, lấy tổng tiền tố $P_r$ trừ đi tổng tiền tố nhỏ nhất trước đó.

Quy hoạch động nhìn bài toán theo cách khác. Gọi $dp_i$ là tổng lớn nhất của một đoạn con kết thúc đúng tại $i$. Đoạn này hoặc chỉ gồm $a_i$, hoặc là một đoạn kết thúc tại $i - 1$ được nối thêm $a_i$; đoạn kết thúc tại $i-1$ tốt nhất có tổng $dp_{i-1}$, nên

Ta chỉ cần giá trị của bước trước, nên một biến là đủ. Cách làm này thường gọi là thuật toán Kadane.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 3e5 + 5;
ll n, a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    ll cur = 0, ans = -1e18;
    for (ll i = 1; i <= n; i++) {
        cur = max(cur, 0LL) + a[i];
        ans = max(ans, cur);
    }
    cout << ans << '\n';
}

ChạyInput8
-2 1 -3 4 -1 2 1 -5

Output6

Độ phức tạp: $O(n)$, với $n = 3 \cdot 10^5$ cần khoảng $6 \cdot 10^5$ phép tính.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, a[100];

signed main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    ll cur = 0, ans = 0;
    for (ll i = 1; i <= n; i++) {
        cur = max(cur, 0LL) + a[i];
        ans = max(ans, cur);
    }
    cout << ans << '\n';
}

ChạyInput3
-3 -1 -2

Output0

Thêm trạng thái khi có thêm thao tác

Đề có thể cho thêm một thao tác, và khi đó trạng thái cần nhớ thêm thao tác đã làm tới đâu. Xét ví dụ sau.

Ví dụĐoạn Nhân Một Lần

Đề. Cho dãy $a_1, \dots, a_n$ ($n \le 3 \cdot 10^5$, $|a_i| \le 10^9$) và số nguyên $x$ ($|x| \le 100$). Được chọn nhiều nhất một đoạn liên tiếp rồi nhân mọi phần tử trong đó với $x$ (cũng có thể không chọn). Sau đó lấy tổng lớn nhất của một đoạn con liên tiếp, đoạn con được phép rỗng (tổng $0$).

Lời giải. Với đoạn được lấy tổng, mỗi phần tử của nó nằm ở một trong ba vùng liên tiếp: trước vùng nhân, trong vùng nhân, hoặc sau vùng nhân; có vùng có thể rỗng. Ta gọi $f_0$, $f_1$, $f_2$ là tổng lớn nhất của một đoạn kết thúc tại vị trí hiện tại, mà phần tử cuối cùng đang ở vùng trước, vùng trong, vùng sau tương ứng.

Khi thêm phần tử $a$, mỗi vùng chỉ có thể tiếp nối từ vùng của nó hoặc vùng ngay trước:

• $f_0 \leftarrow \max(f_0, 0) + a$: vẫn ở vùng trước, hoặc bắt đầu đoạn mới tại $a$.
• $f_1 \leftarrow \max(f_0, f_1, 0) + x \cdot a$: $a$ bị nhân; đoạn đến từ vùng trước, từ chính vùng trong, hoặc bắt đầu tại $a$.
• $f_2 \leftarrow \max(f_1, f_2) + a$: sang vùng sau, từ vùng trong hoặc từ vùng sau.

Đáp án là $0$ (đoạn rỗng) và lớn nhất của các giá trị $f_0$, $f_1$, $f_2$ sau mỗi phần tử. Cả ba cập nhật dùng giá trị cũ của bước trước, nên trong code tính xong rồi mới gán.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 3e5 + 5;
ll n, x, a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    ll f0 = 0, f1 = -1e18, f2 = -1e18, ans = 0;
    for (ll i = 1; i <= n; i++) {
        ll g0 = max(f0, 0LL) + a[i];
        ll g1 = max(max(f0, f1), 0LL) + x * a[i];
        ll g2 = max(f1, f2) + a[i];
        f0 = g0, f1 = g1, f2 = g2;
        ans = max(ans, max(f0, max(f1, f2)));
    }
    cout << ans << '\n';
}

ChạyInput6 -3
4 -5 2 -1 3 -4

Output23

Độ phức tạp: $O(n)$, với $n = 3 \cdot 10^5$ cần khoảng $2 \cdot 10^6$ phép tính.

IIDãy con tăng dài nhất: O(n²)

Ta bắt đầu với cách quy hoạch động thẳng. Gọi $dp_i$ là độ dài dãy con tăng dài nhất kết thúc đúng tại $a_i$. Cần ghi nhớ phần tử cuối 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. 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$, dài nhất có thể là $dp_j$. Vậy

trong đó $\max$ thứ hai lấy giá trị lớn nhất trong các $dp_j$ thỏa điều kiện viết bên dưới, và số $0$ dành cho trường hợp không có $j$ nào. Đáp án là $dp_i$ lớn nhất. Với dãy $5, 2, 8, 6, 3, 6, 9, 7$ ta có $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ừ phần tử có $dp$ lớn nhất theo $par$ rồi đảo lại, ta in được chính dãy con; đó là truy vết (reconstruction).

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 5005;
ll n, a[N], dp[N], par[N], seq[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;
    }
    ll len = 0;
    for (ll i = best; i; i = par[i]) seq[len++] = a[i];
    cout << dp[best] << '\n';
    for (ll i = len - 1; i >= 0; i--) cout << seq[i] << ' ';
    cout << '\n';
}

ChạyInput8
5 2 8 6 3 6 9 7

Output4
2 3 6 9

Độ phức tạp: $O(n^2)$, với $n = 5000$ cần khoảng $1{,}25 \cdot 10^7$ phép tính.

Với $n = 2 \cdot 10^5$ cách này cần tới $2 \cdot 10^{10}$ phép tính, quá chậm.

IIIDãy con tăng dài nhất: O(n log n)

Ta có thể thấy được điểm lãng phí của cách trên: mỗi $a_i$ xét lại mọi $a_j$ đứng trước, trong khi nhiều dãy cùng độ dài chỉ khác nhau ở phần tử cuối. Hai dãy con tăng cùng dài $k$, dãy có phần tử cuối nhỏ hơn dễ được nối thêm hơn: mọi phần tử nối được vào dãy kia thì cũng nối được vào dãy này. Vì vậy, với mỗi độ dài $k$ ta chỉ cần nhớ phần tử cuối nhỏ nhất của một dãy con tăng dài $k$, gọi là $tail_k$ (mảng $tail$ đánh số từ $0$ trong code, nên $tail[k - 1]$ ứng với độ dài $k$).

Mảng $tail$ tăng nghiêm ngặt: một dãy con tăng dài $k + 1$ kết thúc tại $t$ chứa một dãy dài $k$ kết thúc tại giá trị nhỏ hơn $t$. Khi đọc phần tử mới $x$, ta tìm vị trí đầu tiên trong $tail$ có giá trị không nhỏ hơn $x$:

• Nếu không có vị trí nào, $x$ lớn hơn mọi phần tử cuối, ta nối $x$ vào dãy dài nhất và $tail$ dài thêm $1$.
• Nếu có vị trí $p$, thì $x$ là phần tử cuối nhỏ hơn (hoặc bằng) cho dãy dài $p + 1$, nên ghi đè $tail[p] = x$.

Vì $tail$ tăng nên vị trí đó tìm được bằng chặt nhị phân. Độ dài cuối cùng của $tail$ là đáp án. Cần lưu ý $tail$ không phải một dãy con thật của đầu vào: các giá trị trong nó có thể đến từ những dãy khác nhau. Muốn in một dãy tối ưu, ta ghi thêm cho mỗi phần tử vị trí của phần tử đứng trước nó ngay lúc chèn, rồi đi ngược như ở mục trước.

Ví dụNhững Mốc Tăng Dần

Đề. Cho dãy $n \le 2 \cdot 10^5$ số nguyên. In độ dài lớn nhất của một dãy con tăng nghiêm ngặt.

Lời giải. Dùng mảng $tail$ ở trên. Hàm lower_bound trả về vị trí đầu tiên có giá trị không nhỏ hơn $x$, đúng như bước tìm của ta. Với dãy tăng nghiêm ngặt, hai giá trị bằng nhau không được cùng nằm trong một dãy, nên cần lower_bound: khi $x$ bằng một phần tử cuối đã có, ta ghi đè lên chính nó thay vì nối thêm.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, a[N], tail[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    ll len = 0;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        ll p = lower_bound(tail, tail + len, a[i]) - tail;
        tail[p] = a[i];
        if (p == len) len++;
    }
    cout << len << '\n';
}

ChạyInput8
5 1 4 2 3 9 6 7

Output5

Độ phức tạp: $O(n \log n)$, với $n = 2 \cdot 10^5$ cần khoảng $3{,}5 \cdot 10^6$ phép tính.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, a[100], tail[100];

signed main() {
    cin >> n;
    ll len = 0;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        ll p = upper_bound(tail, tail + len, a[i]) - tail;
        tail[p] = a[i];
        if (p == len) len++;
    }
    cout << len << '\n';
}

ChạyInput3
2 2 2

Output3

Cùng ý này còn giải được nhiều bài khác. Ví dụ, cho $n$ khung hình chữ nhật, chọn nhiều khung nhất sao cho chúng lồng được vào nhau: sắp các khung theo chiều rộng tăng dần (với chiều rộng bằng nhau thì xếp chiều cao giảm dần), rồi tìm dãy con tăng dài nhất theo chiều cao.

IVXâu con chung dài nhất

Cho hai xâu $s$ và $t$. Tìm một dãy con chung dài nhất, tức là xâu vừa là dãy con của $s$ vừa là dãy con của $t$ (xóa bớt ký tự nhưng giữ thứ tự), gọi là bài xâu con chung dài nhất (longest common subsequence, LCS). Với $|s| = |t| = n$ có $2^n$ dãy con của mỗi xâu, nên không thể liệt kê.

Trạng thái là một cặp tiền tố: $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$. Xét hai ký tự cuối $s_i$ và $t_j$:

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

Truy vết từ ô $(n, m)$: hai ký tự bằng nhau thì ghi lại ký tự đó và đi chéo; khác nhau thì đi sang ô kề có giá trị lớn hơn (ô trên hoặc ô trái). Mỗi lần ghi, $dp$ giảm đúng $1$ nên ta ghi đúng $dp_{n,m}$ ký tự; đảo ngược xâu ghi được là xong. Cần giữ cả bảng để truy vết.

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

Đề. Cho hai chuỗi $s$ và $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); nếu độ dài lớn nhất bằng $0$ thì in dòng rỗng.

Lời giải. Dùng đúng công thức và cách truy vết ở trên. Bảng có $3001^2 \approx 9 \cdot 10^6$ ô; với kiểu int khoảng $36$ MB. Chuỗi đánh số từ $0$ (s[i - 1]) nhưng bảng đánh số từ $1$, vì $i$ là độ dài của 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

Độ phức tạp: $O(nm)$, với $n = m = 3000$ cần khoảng $9 \cdot 10^6$ phép tính.

VKhoảng cách sửa xâu

Cho hai xâu $A$ và $B$. Mỗi bước được chèn một ký tự vào vị trí bất kỳ, xóa một ký tự, hoặc thay một ký tự bằng ký tự khác, mỗi bước tốn $1$. Tìm số bước ít nhất để biến $A$ thành $B$, gọi là khoảng cách sửa xâu (edit distance). Với $|A|, |B| \le 5000$.

Cũng dùng cặp tiền tố: $dp_{i,j}$ là số bước ít nhất để biến $i$ ký tự đầu của $A$ thành $j$ ký tự đầu của $B$. Biến xâu rỗng thành $j$ ký tự cần $j$ lần chèn, và ngược lại cần $i$ lần xóa, nên $dp_{i,0} = i$ và $dp_{0,j} = j$. Xét hai ký tự cuối $A_i$ và $B_j$:

• Nếu $A_i = B_j$, ta giữ chúng nguyên: $dp_{i,j} = dp_{i-1,j-1}$.
• Nếu khác nhau, bước cuối cùng của một phương án tối ưu là một trong ba loại: xóa $A_i$ (còn biến $i-1$ ký tự đầu thành $j$ ký tự đầu, $dp_{i-1,j}$), chèn $B_j$ vào cuối (còn biến $i$ ký tự đầu thành $j-1$ ký tự đầu, $dp_{i,j-1}$), hoặc thay $A_i$ thành $B_j$ ($dp_{i-1,j-1}$). Tốn thêm $1$ bước:

Mỗi hàng chỉ dùng hàng ngay trước nó, và bài này chỉ hỏi số bước chứ không cần in phương án, nên ta giữ hai hàng thay cho cả bảng $5000 \times 5000$ ô.

Ví dụBiến Đổi Hai Xâu

Đề. Cho hai xâu $A$ và $B$ ($1 \le |A|, |B| \le 5000$, gồm chữ in hoa). Mỗi thao tác chèn, xóa hoặc thay một chữ cái tốn $1$. In số thao tác ít nhất để biến $A$ thành $B$.

Lời giải. Dùng công thức ở trên. Hàng của $i$ lưu ở d[i & 1], hàng trước ở d[(i - 1) & 1]; trước khi tính hàng $i$, đặt ô đầu hàng bằng $i$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
string a, b;
ll d[2][5005];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> a >> b;
    ll n = a.size(), m = b.size();
    for (ll j = 0; j <= m; j++) d[0][j] = j;
    for (ll i = 1; i <= n; i++) {
        ll p = i & 1, q = p ^ 1;
        d[p][0] = i;
        for (ll j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) d[p][j] = d[q][j - 1];
            else d[p][j] = 1 + min(min(d[q][j], d[p][j - 1]), d[q][j - 1]);
        }
    }
    cout << d[n & 1][m] << '\n';
}

ChạyInputSTONE
MONEY

Output3

Độ phức tạp: $O(nm)$ thời gian, $O(m)$ bộ nhớ, với $n = m = 5000$ cần khoảng $2{,}5 \cdot 10^7$ phép tính.

VIĐường đi trên lưới

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.

Gọi $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 từng hàng từ trên xuống, mỗi hàng từ trái sang phải, thì 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$, 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 mỗi ô chọn ô nguồn có $dp$ lớn hơn (đó chính là ô đã cho ra $dp_{i,j}$), ghi lại bước vừa lùi, dừng khi tới $(1, 1)$ rồi đảo chuỗi bước.

#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

Độ phức tạp: $O(RC)$, với $R = C = 100$ cần khoảng $2 \cdot 10^4$ phép tính.

Đường tối ưu đi xuống, phải, phải, xuống, phải: $2 - 1 + 5 - 2 + 6 - 1 = 9$.

Cùng khuôn này, thay max bằng phép cộng và đặt ô cấm bằng $0$ ta đếm được số đường đi.

Ví dụĐường Đi Qua Lưới

Đề. Lưới $n \times n$ ($n \le 1000$), mỗi ô là ô trống . hoặc ô cấm *. Từ ô góc trên bên trái, mỗi bước đi sang phải hoặc xuống dưới, không bước vào ô cấm. Đếm số đường đi tới ô góc dưới bên phải, modulo $10^9 + 7$.

Lời giải. Gọi $dp_{i,j}$ là số đường tới $(i, j)$. Ô cấm có $dp = 0$; ô trống khác ô xuất phát có $dp_{i,j} = dp_{i-1,j} + dp_{i,j-1}$ (lấy dư), vì mọi đường tới $(i, j)$ có đúng một bước cuối, từ ô trên hoặc ô trái. Ô xuất phát có $dp_{1,1} = 1$ nếu nó là ô trống. Viền ngoài bảng bằng $0$, vì không có đường nào đi vào từ ngoài; đây là bài đếm nên viền $0$ mới đúng.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7;
ll n, dp[1005][1005];
char g[1005][1005];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++) cin >> g[i][j];
    if (g[1][1] == '.') dp[1][1] = 1;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++) {
            if (g[i][j] == '*' || (i == 1 && j == 1)) continue;
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
        }
    cout << dp[n][n] << '\n';
}

ChạyInput5
.....
.**..
...*.
*....
.....

Output9

Độ phức tạp: $O(n^2)$, với $n = 1000$ cần khoảng $10^6$ phép tính.

Khi hai người cùng đi từ hai đầu và phải cùng đến một ô, ta có thể xét hai người đi đồng thời từng bước: sau $d$ bước, mỗi người nằm trên đường chéo $d$, nên trạng thái chỉ cần hai tọa độ hàng thay vì bốn tọa độ.