Đăng nhập để tham gia lộ trình luyện tập

QUY HOẠCH ĐỘNG

Quy hoạch động (Dynamic Programming - DP) là cách giải bài bằng việc xác định một tập trạng thái đủ thông tin, viết quan hệ chuyển giữa các trạng thái và tính mỗi trạng thái đúng một lần. Điểm khó nhất không phải viết vòng lặp mà là chọn đúng state: state phải chứa đủ thông tin để mọi lịch sử dẫn tới cùng state có cùng tập lựa chọn tương lai và cùng giá trị tối ưu còn lại. Lộ trình này đi theo đúng 22 giai đoạn từ nền tảng đến các kỹ thuật tối ưu và hybrid nâng cao.

Một bài DP nên được phân tích theo sáu câu hỏi:

1. State là gì?
2. State đã chứa đủ thông tin ảnh hưởng tới tương lai chưa?
3. Transition từ đâu tới đâu?
4. Base case là gì?
5. Thứ tự tính nào bảo đảm mọi dependency đã có?
6. Số trạng thái nhân số chuyển trên mỗi trạng thái có qua giới hạn không?

Nếu lời giải ban đầu là $O(N^2)$ hoặc $O(N^3)$, chưa nên dừng ở việc code. Hãy nhìn lại transition: nó có phải tổng trên đoạn, min/max trên đoạn, truy vấn theo giá trị, đường thẳng $y=mx+b$, cửa sổ trượt, subset, hay một cấu trúc đơn điệu hay không. Đây là điểm nối từ DP cơ bản sang DP tối ưu.

Giai đoạn 0 - ZERO -> HIỂU BẢN CHẤT DP

DP xuất hiện khi bài toán có các bài toán con chồng lặp (overlapping subproblems) và lời giải của bài lớn có thể ghép từ lời giải của bài nhỏ. Ta thường bắt đầu từ đệ quy vét cạn, sau đó nhận ra nhiều lời gọi có cùng tham số.

Ví dụ dạng tuyến tính:

$$dp[i] = \min(dp[i-1] + c_1,\ dp[i-2] + c_2)$$

Trong đó $dp[i]$ là giá trị tốt nhất để đạt tới trạng thái $i$.

Có hai cách triển khai chính.

Memoization giữ cách tư duy đệ quy: chỉ tính state khi cần.

hàm solve(state):
    nếu state là base case:
        trả kết quả base

    nếu state đã được tính:
        trả kết quả đã lưu

    ans = giá trị khởi tạo

    duyệt mọi lựa chọn hợp lệ:
        cập nhật ans từ solve(state mới)

    lưu ans
    trả ans

Tabulation tính từ state nhỏ đến state lớn theo thứ tự dependency.

khởi tạo các base case

duyệt state theo thứ tự hợp lệ:
    dùng các state đã biết
    để cập nhật state hiện tại

trả state chứa đáp án

Nếu có $S$ trạng thái và mỗi trạng thái thử tối đa $T$ chuyển, độ phức tạp thường là:

$$O(S\cdot T)$$

Điều quan trọng là đếm số state thực sự khác nhau, không đếm số lời gọi đệ quy trước memoization.

Một state tốt phải có tính Markov: khi đã biết state hiện tại, quá khứ chi tiết không còn cần thiết để quyết định phần còn lại.

Giai đoạn 1 - DP TUYẾN TÍNH - TAKE/SKIP - PREFIX/SUFFIX

Mẫu cơ bản nhất là dp[i]: đáp án tốt nhất sau khi xử lý prefix đầu tiên gồm $i$ phần tử.

Dạng take/skip thường có công thức:

$$dp[i] = \max(dp[i-1],\ dp[p(i)] + value_i)$$

Trong đó nhánh đầu bỏ phần tử $i$, nhánh sau chọn $i$ và quay về trạng thái trước đó còn tương thích.

Nếu quyết định hiện tại phụ thuộc loại lựa chọn trước, thêm state nhỏ:

$$dp[i][s]$$

với $s$ là trạng thái cuối như màu, hoạt động, số lần đổi, phần dư, hoặc một cờ boolean.

khởi tạo dp[0][...]

duyệt i từ 1 đến n:
    với mỗi trạng thái trước:
        thử các lựa chọn tại i
        nếu hợp lệ:
            cập nhật dp[i][trạng thái mới]

Khi transition chỉ dùng vài lớp trước, có thể rolling array để giảm bộ nhớ từ $O(NS)$ xuống $O(S)$.

Nếu đề yêu cầu in phương án, không chỉ lưu giá trị tối ưu. Cần lưu parent, lựa chọn trước, hoặc đủ thông tin để backtrack.

Sai lầm thường gặp là nhét quá nhiều lịch sử vào state. Nếu một tham số không ảnh hưởng đến các lựa chọn tương lai hoặc có thể suy ra từ các tham số khác, nên bỏ nó.

Giai đoạn 2 - KNAPSACK / SUBSET SUM / COIN CHANGE - FULL BIẾN THỂ

Knapsack là nhóm bài bắt buộc phải phân biệt đúng số lần một vật được dùng và mục tiêu của DP.

0/1 Knapsack

Mỗi vật dùng tối đa một lần.

$$dp[w] = \max(dp[w],\ dp[w-w_i] + v_i)$$

Phải duyệt $w$ giảm:

dp[0] = 0

duyệt từng vật (w_i, v_i):
    duyệt w từ W xuống w_i:
        dp[w] = max(dp[w], dp[w - w_i] + v_i)

Duyệt giảm để trạng thái vừa cập nhật không bị dùng lại trong cùng một vật.

Unbounded Knapsack

Mỗi loại dùng không giới hạn. Duyệt capacity tăng:

duyệt từng loại:
    duyệt w từ w_i đến W:
        cập nhật dp[w] từ dp[w - w_i]

Subset Sum

Chỉ cần biết tổng $s$ có đạt được hay không:

$$possible[s] \in \{false,true\}$$

possible[0] = true

duyệt từng x:
    duyệt s giảm:
        nếu possible[s - x]:
            possible[s] = true

Coin Change có thứ tự và không thứ tự

Nếu thứ tự đồng xu tạo nghiệm khác nhau, duyệt tổng ngoài và coin trong.

ways[0] = 1

duyệt sum tăng:
    duyệt từng coin:
        nếu sum >= coin:
            ways[sum] += ways[sum - coin]

Nếu chỉ quan tâm tổ hợp không xét thứ tự, duyệt coin ngoài.

ways[0] = 1

duyệt từng coin:
    duyệt sum từ coin đến S:
        ways[sum] += ways[sum - coin]

Hai đoạn mã có cùng công thức cộng nhưng ý nghĩa khác nhau vì thứ tự vòng lặp khác nhau.

Value-DP

Khi trọng lượng $W$ quá lớn nhưng tổng value nhỏ, đổi state:

$$dp[v] = \text{trọng lượng nhỏ nhất để đạt tổng giá trị } v$$

Cuối cùng lấy $v$ lớn nhất sao cho:

$$dp[v]\le W$$

Bounded Knapsack

Nếu loại $i$ có $c_i$ bản, có thể phân rã:

$$c_i = 1 + 2 + 4 + \cdots + r$$

để chuyển thành một số vật 0/1. Ở mức cao hơn có thể tối ưu theo lớp phần dư bằng monotone queue.

Offset cho tổng âm

Nếu tổng có thể âm trong đoạn $[-M,M]$, ánh xạ:

$$index = sum + M$$

Không dùng chỉ số âm trực tiếp.

Giai đoạn 3 - GRID DP - DAG DP - ĐỒ THỊ ẨN

Nhiều bài DP thực chất là tìm đường trên một DAG. Mỗi state là một đỉnh, mỗi transition là một cạnh.

Nếu mọi cạnh đi từ state nhỏ sang state lớn theo một thứ tự nào đó, ta có thể DP theo thứ tự topo.

Với lưới chỉ đi xuống và sang phải:

$$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$

nếu ô $(i,j)$ không bị chặn.

dp[start] = 1

duyệt ô theo thứ tự hàng rồi cột:
    nếu ô bị chặn:
        bỏ qua

    cộng từ các predecessor hợp lệ

Với min/max path, thay phép cộng số cách bằng min hoặc max trên giá trị đường đi.

Điểm quan trọng là nhận ra thứ tự dependency. Nếu state có cạnh quay về state chưa tính, không thể tabulation theo thứ tự đó.

DP trên DAG tổng quát:

$$dp[v] = \max_{u\to v}(dp[u] + w(u,v))$$

topo = thứ tự topo của DAG

duyệt v theo topo:
    duyệt cạnh v -> to:
        relax dp[to] từ dp[v]

Nếu đồ thị có chu trình nhưng bài có thể nén thành DAG, một hướng thường gặp là gom SCC trước rồi DP trên condensation DAG.

Grid DP cũng có thể cần nhiều bảng theo hướng. Một số bài yêu cầu tính từ bốn góc, từ đầu và cuối, hoặc hai người di chuyển đồng thời. Khi đó cần tách rõ mỗi bảng đại diện cho hướng nào.

Giai đoạn 4 - SEQUENCE DP - LIS/LDS/LCIS/MAX RANGE

LIS $O(N^2)$

Đặt:

$$dp[i] = \text{độ dài LIS kết thúc tại } i$$

Ta có:

$$dp[i] = 1 + \max_{j<i,\ a_j<a_i} dp[j]$$

Độ phức tạp $O(N^2)$.

LIS $O(N\log N)$

Dùng mảng tails, trong đó tails[len-1] là giá trị cuối nhỏ nhất có thể của dãy tăng độ dài len.

tails = rỗng

duyệt x:
    pos = lower_bound(tails, x)

    nếu pos ở cuối:
        thêm x
    ngược lại:
        tails[pos] = x

tails cho độ dài LIS nhưng bản thân nó không nhất thiết là một LIS thực tế. Muốn reconstruct cần thêm predecessor và vị trí đại diện.

Weighted LIS

Thay độ dài bằng trọng số:

$$dp[i] = weight_i + \max_{j<i,\ a_j<a_i} dp[j]$$

Nếu chỉ số theo giá trị có thể nén tọa độ, phần $\max$ có thể được lấy bằng Fenwick Tree hoặc Segment Tree.

Bitonic

Tính LIS kết thúc tại $i$ và LIS theo chiều ngược bắt đầu tại $i$, rồi ghép tại tâm. Cần kiểm tra công thức trừ $1$ để không đếm tâm hai lần.

Maximum Subarray

Kadane:

$$bestEnd_i = \max(a_i,\ bestEnd_{i-1}+a_i)$$ $$answer = \max_i bestEnd_i$$

Nếu dãy có số âm và phép nhân, maximum product cần giữ cả min lẫn max vì số âm có thể đổi vai trò:

$$mx_i = \max(a_i,\ a_i mx_{i-1},\ a_i mn_{i-1})$$ $$mn_i = \min(a_i,\ a_i mx_{i-1},\ a_i mn_{i-1})$$

Giai đoạn 5 - STRING DP - LCS/EDIT/PALINDROME/SUBSEQUENCE

LCS

Đặt $dp[i][j]$ là độ dài LCS của hai prefix $A[1..i]$ và $B[1..j]$.

Nếu $A_i=B_j$:

$$dp[i][j]=dp[i-1][j-1]+1$$

Nếu khác:

$$dp[i][j]=\max(dp[i-1][j],dp[i][j-1])$$

Muốn dựng một LCS, backtrack từ $(n,m)$.

Edit Distance

$$dp[i][j] = \text{số phép sửa ít nhất để đổi } A[1..i] \text{ thành } B[1..j]$$

Nếu ký tự cuối bằng nhau:

$$dp[i][j]=dp[i-1][j-1]$$

Nếu khác:

$$dp[i][j] = 1+\min \begin{cases} dp[i-1][j] & \text{xóa}\\ dp[i][j-1] & \text{chèn}\\ dp[i-1][j-1] & \text{thay} \end{cases}$$

Nếu chỉ cần giá trị, có thể rolling hai hàng. Nếu cần in edit script, thường phải giữ parent hoặc bảng đầy đủ.

Đếm subsequence

Khi đếm số cách chuỗi $T$ xuất hiện như subsequence của $S$, state tự nhiên là hai prefix. Cần dùng kiểu dữ liệu đủ lớn nếu đề không modulo.

Palindrome interval DP

Đặt:

$$dp[l][r]$$

cho substring $S[l..r]$.

Nếu hai đầu bằng nhau, thường co vào:

$$dp[l][r]\leftarrow dp[l+1][r-1]$$

Nếu khác, transition tùy objective: bỏ trái, bỏ phải, chèn, xóa hoặc thay.

Word Break / String Segmentation

Đặt $dp[i]$ cho prefix kết thúc tại $i$. Transition thử các từ kết thúc ở $i$. Nếu từ điển lớn, Trie hoặc automaton giúp tránh quét toàn bộ từ điển ở mỗi vị trí.

Giai đoạn 6 - INTERVAL / RANGE DP - CHIA ĐOẠN - GAME ĐOẠN

State điển hình:

$$dp[l][r]$$

Độ dài đoạn tăng dần là thứ tự tính tự nhiên.

duyệt len từ nhỏ đến lớn:
    duyệt l:
        r = l + len - 1
        tính dp[l][r] từ các đoạn ngắn hơn

Merge DP

Ví dụ dạng gộp:

$$dp[l][r] = \min_{l\le k<r} \left( dp[l][k] + dp[k+1][r] + cost(l,r) \right)$$

Nếu cost(l,r) là tổng đoạn, nên dùng prefix sum để lấy $O(1)$.

Matrix Chain

Nếu ma trận thứ $i$ có kích thước $p_{i-1}\times p_i$:

$$dp[l][r] = \min_k \left( dp[l][k] + dp[k+1][r] + p_{l-1}p_kp_r \right)$$

Game hai đầu

Với game zero-sum, dùng chênh lệch điểm:

$$dp[l][r] = \max \left( a_l-dp[l+1][r],\ a_r-dp[l][r-1] \right)$$

Cách biểu diễn này thường gọn hơn lưu điểm của hai người riêng.

Last-action DP

Một kỹ thuật quan trọng là đảo tư duy: thay vì hỏi phần tử nào xử lý đầu tiên, chọn phần tử được xử lý cuối cùng trong đoạn. Khi phần tử cuối được cố định, hai phía có thể trở nên độc lập.

Circular interval

Có thể nhân đôi mảng và xét mọi đoạn độ dài $n$, hoặc cố định một điểm phá vòng. Không nên thêm chiều state vòng tròn nếu một biến đổi đơn giản có thể làm bài trở lại tuyến tính.

Giai đoạn 7 - PARTITION / SCHEDULING / SEGMENTATION DP

Nhóm này thường chia prefix $1..i$ thành các đoạn.

Dạng cơ bản:

$$dp[i] = \min_{0\le j<i} \left( dp[j]+cost(j+1,i) \right)$$

Nếu cần đúng $K$ nhóm:

$$dp[g][i] = \min_{j<i} \left( dp[g-1][j]+cost(j+1,i) \right)$$

Đây là recurrence nền cho Divide & Conquer DP Optimization ở giai đoạn sau.

Weighted Interval Scheduling

Sắp xếp công việc theo thời điểm kết thúc. Với công việc $i$, tìm $p(i)$ là công việc gần nhất kết thúc trước khi $i$ bắt đầu.

$$dp[i] = \max \left( dp[i-1],\ dp[p(i)] + value_i \right)$$

$p(i)$ thường tìm bằng binary search.

Precompute cost đoạn

Nếu transition dùng $cost(l,r)$ nhiều lần, hãy tách bài thành hai bước:

1. tính hoặc hỗ trợ truy vấn cost(l,r) nhanh;
2. chạy DP partition.

Độ phức tạp tổng không chỉ phụ thuộc số state mà còn phụ thuộc chi phí lấy cost.

Giai đoạn 8 - TREE DP - SUBTREE / INDEPENDENT SET / MATCHING

Root cây tại một đỉnh tùy ý. Tính từ lá lên bằng DFS hậu thứ tự.

Mẫu chọn/không chọn node:

$$dp[u][0],\quad dp[u][1]$$

Ví dụ Independent Set:

$$dp[u][1] = \prod_{v\text{ là con của }u} dp[v][0]$$ $$dp[u][0] = \prod_v \left( dp[v][0]+dp[v][1] \right)$$

dfs(u, parent):
    khởi tạo trạng thái của u

    duyệt child v:
        dfs(v, u)
        gộp trạng thái của v vào u

Điểm cốt lõi là xác định quan hệ giữa state của cha và state của con.

Tree Matching

State có thể mô tả u đã ghép với cha hay chưa, hoặc có cạnh nào từ u xuống con được chọn hay chưa. Phải tránh chọn hai cạnh cùng chạm một đỉnh.

Dominating / Cover

Nhiều bài cần ba trạng thái thay vì hai:

• node được chọn;
• node không chọn nhưng đã được con che phủ;
• node chưa được che phủ và cần cha xử lý.

Tree Knapsack

Đặt:

$$dp[u][k]$$

là đáp án tốt nhất khi chọn $k$ đơn vị trong subtree của $u$.

Khi gộp một child, transition giống knapsack/convolution:

$$new[k+x] = \operatorname{best} \left( new[k+x], dp_u[k]+dp_v[x] \right)$$

Tổng kích thước các vòng merge phải được phân tích cẩn thận.

Giai đoạn 9 - REROOTING / TREE DP NÂNG CAO

Tree DP thông thường tính tốt cho một root. Rerooting tính đáp án cho mọi root.

Mô hình phổ biến gồm hai phần:

• down[u]: contribution từ subtree của $u$;
• up[u]: contribution từ phía ngoài subtree của $u$.

Khi chuyển root từ $u$ sang child $v$, cần loại contribution của $v$ khỏi tổng của $u$, rồi truyền phần còn lại xuống $v$.

Nếu phép gộp là tổng:

$$outside_v = total_u - contribution_v$$

Nếu không thể chia hoặc nghịch đảo, dùng prefix/suffix trên danh sách children.

tính down[u] cho mọi u bằng DFS thứ nhất

DFS thứ hai tại u:
    tạo prefix contribution của children
    tạo suffix contribution của children

    với mỗi child v:
        lấy tổng mọi child khác v bằng prefix + suffix
        tạo up[v]
        tiếp tục reroot xuống v

Với bài lấy max, thường giữ hai contribution lớn nhất. Khi đi sang child đang giữ max lớn nhất, dùng max lớn thứ hai.

Rerooting tốt thường đạt $O(N)$ hoặc $O(N\log N)$ thay vì chạy lại DFS từ mọi root.

Giai đoạn 10 - BITMASK / SUBSET DP - TSP/MATCHING/HAMILTONIAN

Khi $N$ nhỏ, một tập phần tử có thể mã hóa bằng mask từ $0$ đến $2^N-1$.

DP theo mask

$$dp[mask]$$

hoặc:

$$dp[mask][last]$$

nếu cần biết phần tử cuối.

Held-Karp TSP

$$dp[mask][v] = \min_{u\in mask,\ u\ne v} \left( dp[mask\setminus\{v\}][u] + dist[u][v] \right)$$

Số trạng thái $O(N2^N)$, mỗi trạng thái thử $O(N)$ chuyển:

$$O(N^2 2^N)$$

Matching

Nếu popcount(mask) cho biết đã ghép bao nhiêu người, không cần lưu thêm chỉ số người đang xét.

dp[0] = 1

duyệt mask:
    i = popcount(mask)

    thử mọi j chưa có trong mask:
        nếu i có thể ghép với j:
            dp[mask | (1 << j)] += dp[mask]

Enumerate submask

Mẫu chuẩn:

sub = mask
trong khi sub > 0:
    xử lý sub
    sub = (sub - 1) & mask

Tổng số cặp (mask, submask) là:

$$\sum_{mask} 2^{popcount(mask)} = 3^N$$

Vì vậy subset partition kiểu duyệt mọi submask thường là $O(3^N)$, không phải $O(4^N)$.

Giai đoạn 11 - DIGIT DP - TIGHT / LEADING ZERO / AUTOMATON

Digit DP dùng để đếm hoặc tính tổng các số trong $[0,N]$ thỏa điều kiện theo chữ số.

State điển hình:

$$dp[pos][tight][started][state]$$

Trong đó:

• pos: vị trí chữ số;
• tight: prefix hiện tại còn bằng prefix của $N$ hay đã nhỏ hơn;
• started: đã bắt đầu số thực hay vẫn đang ở leading zero;
• state: phần dư, tổng chữ số, chữ số trước, mask đã dùng, trạng thái automaton,...

Transition chọn chữ số $d$ trong khoảng:

$$0\le d\le limit$$

với:

$$limit= \begin{cases} digit_N[pos] & tight=1\\ 9 & tight=0 \end{cases}$$

dfs(pos, tight, started, state):
    nếu pos == số chữ số:
        trả 1 nếu state cuối hợp lệ

    nếu state memo được:
        trả memo

    limit = chữ số N[pos] nếu tight
            ngược lại 9

    ans = 0

    duyệt d từ 0 đến limit:
        tạo started mới
        tạo state mới
        tạo tight mới
        ans += dfs(...)

    lưu và trả ans

Đếm trên đoạn:

$$answer(L,R)=F(R)-F(L-1)$$

Nếu cần vừa đếm vừa tính tổng giá trị số, state có thể trả một cặp (count, sum). Khi nối chữ số $d$, contribution vị trí phải được cộng theo số lượng suffix tương ứng.

Leading zero phải được xử lý rõ để không vô tình coi các số có độ dài ngắn hơn là các số có nhiều chữ số 0 đầu.

Giai đoạn 12 - PROFILE / BROKEN PROFILE / PLUG DP

Khi một chiều của grid nhỏ, có thể mã hóa trạng thái biên giữa phần đã xử lý và chưa xử lý.

Broken Profile

Với chiều rộng $W$ nhỏ, mask có $W$ bit:

$$0\le mask<2^W$$

Ví dụ lát domino theo cột:

$$dp[col][mask]$$

mask mô tả các ô ở cột hiện tại đã bị chiếm bởi domino từ cột trước.

hàm sinh(row, curMask, nextMask):
    nếu row == H:
        cộng dp[col][curMask] vào dp[col+1][nextMask]
        trả về

    nếu ô row đã bị chiếm:
        sinh(row + 1, curMask, nextMask)
    ngược lại:
        thử đặt domino dọc nếu hợp lệ
        thử đặt domino ngang và bật bit ở nextMask

Một tối ưu thực dụng là precompute tất cả nextMask hợp lệ cho từng mask, sau đó DP theo cột chỉ duyệt danh sách chuyển đã chuẩn bị.

Row Profile nhiều hàng

Có bài state hiện tại phụ thuộc cả một hoặc hai hàng trước. Khi đó key có thể là (maskPrev, maskPrev2).

Plug DP

Khi cần duy trì liên thông/Hamiltonian, mỗi vị trí trên frontier không chỉ là 0/1 mà mang nhãn thành phần kết nối. Cần chuẩn hóa nhãn để hai trạng thái tương đương có cùng encoding.

Profile DP mạnh khi chiều nhỏ; nếu cả hai chiều lớn, $2^W$ hoặc số trạng thái plug sẽ bùng nổ.

Giai đoạn 13 - PROBABILITY / EXPECTATION / GAME DP

Probability DP

Nếu $dp[state]$ là xác suất đạt mục tiêu từ state:

$$dp[s] = \sum_t P(s\to t)\cdot dp[t]$$

Trên DAG, có thể tính theo thứ tự dependency.

Expected Value

Nếu $E[s]$ là số bước kỳ vọng còn lại:

$$E[s] = 1+\sum_t P(s\to t)E[t]$$

Nếu transition có self-loop:

$$E[s] = 1+pE[s]+\sum_{t\ne s}P(s\to t)E[t]$$

Phải chuyển vế:

$$E[s] = \frac{ 1+\sum_{t\ne s}P(s\to t)E[t] }{ 1-p }$$

Không được memoize trực tiếp công thức còn chứa chính $E[s]$ ở vế phải.

Win/Lose Game DP

State thắng nếu tồn tại một nước đi sang state thua:

$$win[s] = \exists t:\ s\to t \land \neg win[t]$$

Score-difference Game

Với game zero-sum, lưu hiệu điểm người hiện tại trừ đối thủ thường làm state nhỏ hơn:

$$dp[s] = \max_{move} \left( gain(move)-dp[next] \right)$$

Minimax

Nếu một người tối đa hóa còn người kia tối thiểu hóa, transition phụ thuộc lượt. Chỉ dùng DP/memoization nếu không gian state hữu hạn và lặp lại đủ nhiều.

Giai đoạn 14 - COMBINATORIAL DP / COUNTING CONSTRUCTIONS

Nhóm này đếm số cấu hình thay vì tối ưu giá trị.

State thường gồm nhiều tham số nhỏ như:

$$dp[i][sum],\quad dp[i][k],\quad dp[i][balance],\quad dp[i][runs]$$

Bounded composition

Số cách phân $K$ đơn vị cho $N$ nhóm, nhóm $i$ nhận từ $0$ đến $a_i$:

$$dp[i][s] = \sum_{x=0}^{a_i} dp[i-1][s-x]$$

Transition trực tiếp là $O(NK\max a_i)$. Có thể tối ưu bằng prefix sum:

$$dp[i][s] = pref[i-1][s] - pref[i-1][s-a_i-1]$$

Bracket DP tuyến tính

Với chuỗi ngoặc xây từ trái sang phải, state balance là số ngoặc mở chưa đóng.

Điều kiện:

$$balance\ge 0$$

và cuối cùng:

$$balance=0$$

Permutation DP

Nhiều bài đếm permutation có state theo số phần tử đã đặt và một thống kê nhỏ như inversion, số component, dấu quan hệ trước.

Cần luôn hỏi: liệu công thức tổ hợp đóng có thay DP được không? Ngược lại, nếu ràng buộc làm công thức tổ hợp khó tách, DP có thể là cách tự nhiên hơn.

Giai đoạn 15 - THIẾT KẾ STATE NÂNG CAO - DROP DIMENSION / OFFSET / SPARSE MEMO / EGG DROPPING

Mục tiêu của giai đoạn này là giảm không gian state trước khi tối ưu transition.

Drop Dimension

Nếu một tham số có thể suy từ các tham số khác và invariant, không lưu nó.

Ví dụ nếu tổng số bước đã biết từ i, và hai loại hành động có số lượng liên hệ:

$$count_B = i-count_A$$

thì không cần lưu cả hai.

Reparameterization

Đôi khi state tự nhiên theo đề quá lớn. Hãy đổi câu hỏi.

Egg Dropping là ví dụ điển hình. Thay vì:

$$dp[floors][eggs]$$

là số lần thử ít nhất, dùng:

$$f[d][e]$$

là số tầng tối đa kiểm tra được với $d$ lần thử và $e$ quả trứng.

Recurrence:

$$f[d][e] = 1+f[d-1][e-1]+f[d-1][e]$$

Một lần thả chia thành:

• vỡ: kiểm tra được phần dưới;
• không vỡ: kiểm tra được phần trên;
• cộng $1$ cho tầng hiện tại.

State mới thường nhỏ hơn rất nhiều khi đáp án số lần thử nhỏ.

Sparse Memo

Nếu không gian lý thuyết lớn nhưng chỉ ít state được chạm tới, dùng hash map/memo sparse thay vì cấp cả mảng.

Coordinate Compression

Nếu transition phụ thuộc thứ tự của giá trị chứ không cần khoảng cách tuyệt đối, nén tọa độ:

$$value \to rank(value)$$

Finite-state DP

Nếu state thực chỉ có vài trăm cấu hình dù thời gian rất dài, có thể xem toàn bộ như một automaton nhỏ. Đây là cầu nối sang matrix exponentiation.

Giai đoạn 16 - TỐI ƯU TRANSITION - PREFIX SUM / BINARY SEARCH / MONOTONE QUEUE / BITSET

Bước đầu luôn viết recurrence chậm nhưng đúng. Sau đó tìm cấu trúc trong tập predecessor.

Prefix Sum Optimization

Nếu:

$$dp[i][x] = \sum_{y=L(x)}^{R(x)} prev[y]$$

thì dùng prefix:

$$pref[t]=\sum_{y\le t} prev[y]$$

và:

$$dp[i][x] = pref[R(x)]-pref[L(x)-1]$$

Transition từ $O(K)$ xuống $O(1)$.

Binary Search Jump

Nếu predecessor hợp lệ tạo thành một prefix/suffix sau khi sort, tìm biên bằng binary search rồi dùng DP prefix.

Monotone Queue DP

Nếu:

$$dp[i] = value_i+ \max_{j\in[i-K,i-1]} prev[j]$$

thì deque duy trì các prev[j] theo thứ tự giảm.

deque rỗng

duyệt i tăng:
    bỏ đầu deque nếu chỉ số đã ra khỏi cửa sổ

    dp[i] = value[i] + prev[deque.front]

    trong khi cuối deque có giá trị <= giá trị mới:
        pop_back

    push chỉ số mới

Mỗi chỉ số vào và ra deque tối đa một lần, nên tổng là $O(N)$.

Bitset

Subset sum boolean có thể viết:

$$bits \leftarrow bits \lor (bits \ll x)$$

Về bản chất vẫn là cùng recurrence, nhưng xử lý song song theo word của máy.

Đây là tối ưu implementation, không phải một bài toán khác.

Giai đoạn 17 - DP + DATA STRUCTURE

Khi recurrence có dạng:

$$dp[i] = base_i+ \operatorname{best}_{j\in S_i} dp[j]$$

và $S_i$ là một miền theo giá trị hoặc tọa độ, cấu trúc dữ liệu có thể thay vòng quét predecessor.

Fenwick Tree

Phù hợp với prefix sum/max sau nén tọa độ.

Ví dụ weighted LIS:

$$dp[i] = w_i+ \max_{a_j<a_i} dp[j]$$

Nén $a_i$ thành rank, query max trên prefix [1, rank(a_i)-1], rồi update tại rank(a_i).

Segment Tree

Dùng khi cần range min/max tổng quát hơn:

$$\max_{x\in[L_i,R_i]} best[x]$$

Mỗi state thường query $O(\log N)$ rồi update $O(\log N)$.

Best-two trick

Nếu chỉ cần giá trị tốt nhất nhưng phải loại một loại/màu cụ thể, đôi khi không cần cây. Giữ hai candidate tốt nhất thuộc hai nhóm khác nhau để truy vấn "tốt nhất không cùng màu" trong $O(1)$.

Ordered Set / Balanced Tree

Hữu ích khi state khả thi thay đổi động và cần predecessor/successor.

Nguyên tắc: đừng dùng Segment Tree chỉ vì bài có DP. Hãy xác định chính xác phép truy vấn cần thiết rồi chọn cấu trúc nhỏ nhất đủ dùng.

Giai đoạn 18 - CONVEX DP OPTIMIZATION - CHT / LI CHAO / SLOPE TRICK

Có hai họ khác nhau.

Convex Hull Trick cho recurrence tuyến tính hóa được

Ví dụ:

$$dp[i] = \min_{j<i} \left( dp[j]+(x_i-x_j)^2+C \right)$$

Khai triển:

$$dp[i] = x_i^2+C+ \min_j \left( dp[j]+x_j^2-2x_ix_j \right)$$

Với mỗi $j$, tạo đường:

$$y=m_jx+b_j$$

trong đó:

$$m_j=-2x_j$$ $$b_j=dp[j]+x_j^2$$

Query tại $x=x_i$.

Nếu slope và query có thứ tự đơn điệu, có thể dùng hull deque tối ưu. Nếu thứ tự bất kỳ, Li Chao Tree là lựa chọn tổng quát hơn.

Phải xử lý cẩn thận:

• hai đường cùng slope;
• overflow khi nhân;
• min hay max;
• miền $x$;
• thứ tự thêm đường/query.

Slope Trick

Họ thứ hai không phải "line query". DP được xem như một hàm convex piecewise-linear theo một biến.

Các thao tác thường gặp:

• cộng $|x-a|$;
• lấy prefix minimum hoặc suffix minimum;
• dịch miền;
• clamp slope;
• merge các container breakpoint.

Priority queue thường được dùng để lưu breakpoint thay vì lưu toàn bộ hàm.

Không nên trộn Slope Trick và CHT thành một template duy nhất: chúng tối ưu hai cấu trúc recurrence khác nhau.

Giai đoạn 19 - DIVIDE & CONQUER DP / KNUTH / MONGE

Divide & Conquer DP Optimization

Recurrence lớp:

$$dp[g][i] = \min_{j<i} \left( prev[j]+C(j+1,i) \right)$$

Gọi:

$$opt[g][i]$$

là vị trí $j$ tối ưu.

Nếu có tính đơn điệu:

$$opt[g][i]\le opt[g][i+1]$$

ta tính một hàng bằng chia để trị:

compute(L, R, optL, optR):
    nếu L > R:
        trả về

    mid = (L + R) / 2

    best = vô cùng
    bestPos = -1

    duyệt k từ optL đến min(mid - 1, optR):
        thử prev[k] + cost(k + 1, mid)
        cập nhật best và bestPos

    dp[mid] = best

    compute(L, mid - 1, optL, bestPos)
    compute(mid + 1, R, bestPos, optR)

Không được áp dụng chỉ vì recurrence có dạng partition. Cần có căn cứ cho monotone optimum.

Knuth Optimization

Với interval DP:

$$dp[l][r] = \min_{k\in[l,r]} \left( dp[l][k]+dp[k][r]+C(l,r) \right)$$

Trong dạng phù hợp, nếu:

$$opt[l][r-1] \le opt[l][r] \le opt[l+1][r]$$

thì chỉ cần thử $k$ trong khoảng hẹp đó, đưa nhiều bài $O(N^3)$ về $O(N^2)$.

Monge / Quadrangle Inequality

Monotonicity của opt thường đến từ cấu trúc Monge hoặc quadrangle inequality của cost. Đây là điều kiện toán học, không phải đặc điểm cú pháp của code.

Trình tự đúng:

1. viết recurrence chậm;
2. xác định cost;
3. chứng minh hoặc kiểm tra điều kiện đơn điệu;
4. mới áp dụng optimization.

Giai đoạn 20 - MATRIX EXPONENTIATION / AUTOMATON DP / LINEAR RECURRENCE

Nếu state nhỏ nhưng số bước $N$ cực lớn, và transition không đổi theo thời gian, viết:

$$v_{t+1}=M v_t$$

Suy ra:

$$v_N=M^N v_0$$

Tính $M^N$ bằng lũy thừa nhị phân trong:

$$O(S^3\log N)$$

với ma trận $S\times S$ theo phép nhân ma trận thường.

result = ma trận đơn vị
base = M
k = N

trong khi k > 0:
    nếu k lẻ:
        result = result * base

    base = base * base
    k = k / 2

Counting Walks

Ma trận kề $A$ có tính chất:

$$(A^k)_{ij}$$

là số walk độ dài đúng $k$ từ $i$ đến $j$ khi phép toán dùng cộng/nhân thông thường.

Min-plus Matrix

Nếu cần chi phí nhỏ nhất với đúng $k$ cạnh, thay đại số thường bằng semiring min-plus:

$$(C)_{ij} = \min_t (A_{it}+B_{tj})$$

Lúc đó "lũy thừa ma trận" chính là tăng tốc DP theo số bước.

Automaton DP

Nếu điều kiện chuỗi có thể biểu diễn bằng KMP automaton hoặc DFA nhỏ, mỗi state là trạng thái automaton. Với độ dài vừa, DP theo vị trí; với độ dài cực lớn, nâng transition thành ma trận và exponentiate.

Linear Recurrence

Fibonacci và recurrence bậc cố định có thể viết bằng companion matrix. Một số bài còn có kỹ thuật nhanh hơn như fast doubling hoặc các phương pháp recurrence chuyên dụng; cần chọn công cụ theo cấu trúc cụ thể.

Giai đoạn 21 - SUBSET TRANSFORMS / STEINER / WQS-ALIENS / HYBRID DP

Đây là nhóm pattern cao cấp, mục tiêu chính là nhận dạng khi DP cơ bản cần ghép với một kỹ thuật khác.

SOS DP

Cho mảng theo mask, muốn tổng trên mọi submask:

$$F[mask] = \sum_{sub\subseteq mask} A[sub]$$

Ta có thể biến đổi trong $O(N2^N)$:

F = A

duyệt bit i:
    duyệt mask:
        nếu bit i bật trong mask:
            F[mask] += F[mask ^ (1 << i)]

Biến thể tương tự dùng cho supermask, max/min, hoặc lan truyền thông tin khả thi.

Steiner Tree Subset DP

Với $K$ terminal nhỏ:

$$dp[mask][v]$$

là chi phí nhỏ nhất nối các terminal trong mask và có điểm hợp tại $v$.

Hai bước transition chính:

Ghép hai subset tại cùng $v$:

$$dp[mask][v] = \min_{sub\subset mask} \left( dp[sub][v]+dp[mask\setminus sub][v] \right)$$

Sau đó chạy shortest-path relaxation để truyền giá trị qua graph.

WQS / Aliens Trick

Khi cần tối ưu với đúng $K$ nhóm nhưng bài unconstrained dễ hơn, thêm penalty $\lambda$ cho mỗi nhóm:

$$modifiedCost = originalCost+\lambda\cdot groups$$

Chạy DP trả về cả:

• giá trị đã cộng penalty;
• số nhóm tương ứng.

Sau đó binary search $\lambda$ để ép số nhóm về quanh $K$.

Kỹ thuật này chỉ đúng khi cấu trúc đáp án theo penalty có tính đơn điệu phù hợp.

Hybrid DP

DP có thể là một tầng trong lời giải:

• SCC rồi DP trên DAG;
• Dijkstra rồi DP theo shortest-path order;
• DP + Flow;
• DP + Meet-in-the-Middle;
• DP + Fenwick/Segment Tree;
• DP + CHT;
• DP + automaton;
• DP + convolution.

Không nên cố "ép" mọi bài vào DP. Một phản xạ quan trọng ở giai đoạn cuối là nhận ra boundary: khi Greedy, shortest path, flow, matching, FFT/NTT hay một cấu trúc khác mới là công cụ chính.

CHECKLIST NHẬN DẠNG DP TRƯỚC KHI CODE

Khi gặp bài mới, tự trả lời lần lượt:

1. Brute force đang quyết định theo chuỗi lựa chọn nào?
2. Hai nhánh khác nhau khi nào gặp lại cùng phần còn lại?
3. Thông tin tối thiểu nào của quá khứ quyết định toàn bộ tương lai?
4. Có tham số nào suy ra được từ invariant để bỏ khỏi state?
5. Transition là pull từ predecessor hay push sang successor?
6. Dependency có DAG không? Thứ tự tính nào hợp lệ?
7. Objective là min, max, count, existence, probability, expectation hay tuple?
8. Có yêu cầu reconstruction, số nghiệm tối ưu, tie-break hoặc k-th solution không?
9. Số state và số transition có qua giới hạn không?
10. Transition có phải range sum/min/max, sliding window, line query, subset enumeration hay convolution không?
11. Có thể rolling array, sparse memo, coordinate compression hoặc bitset không?
12. Bài có thực sự nên dùng DP hay một thuật toán khác tự nhiên hơn?

QUY TRÌNH TỐI ƯU DP

Không tối ưu trước khi recurrence đúng.

Bước 1:
    viết brute force hoặc recurrence trực tiếp

Bước 2:
    xác định state và dependency

Bước 3:
    memoize hoặc tabulate
    tính đúng độ phức tạp

Bước 4:
    nếu chậm:
        nhìn cấu trúc của tập predecessor

Bước 5:
    chọn tối ưu phù hợp:
        prefix sum
        binary search
        monotone queue
        bitset
        Fenwick / Segment Tree
        CHT / Li Chao
        Divide & Conquer DP
        Knuth
        Matrix exponentiation
        subset transform
        kỹ thuật khác

Bước 6:
    kiểm tra lại invariant và điều kiện đúng của tối ưu

Mục tiêu cuối cùng không phải thuộc càng nhiều template càng tốt. Mục tiêu là khi gặp một bài mới, tự dựng được state đủ thông tin, transition đúng, thứ tự dependency đúng, đánh giá được độ phức tạp và nhận ra chính xác cấu trúc nào có thể dùng để tối ưu.