Quy Hoạch Động 1D

1. Bản chất vấn đề & cầu nối từ đệ quy sang quy hoạch động

Trong Chuyên đề 10 và 12, ta đã chứng kiến hiện tượng Bùng nổ Không gian Trạng thái (Combinatorial Explosion) khi duyệt đệ quy phân nhánh:

• Khi tính số Fibonacci $F(N) = F(N-1) + F(N-2)$, trạng thái $F(3)$ bị tính lại $2$ lần, $F(2)$ bị tính lại $3$ lần. Độ phức tạp thời gian tăng vọt lên cấp số nhân $\Theta(\varphi^N) \approx \Theta(1.618^N)$.
• Nguyên nhân gốc rễ: Hàm đệ quy thuần túy không có cơ chế "ghi nhớ" (Memory). Mỗi lần bước vào một nhánh mới, nó xem bài toán con đó như một thực thể hoàn toàn xa lạ và tính toán lại từ đầu.

Quy Hoạch Động (Dynamic Programming - DP) giải quyết vấn đề này bằng nguyên lý cốt lõi:

DP loại bỏ việc tính toán lại các bài toán con trùng lặp bằng cách lưu trữ kết quả vào Bảng phương án (DP Table) và tái sử dụng ngay lập tức trong $\mathcal{O}(1)$.

2. Khung phương pháp luận: 7 bước DP state invariant

Để giải quyết chính xác bất kỳ bài toán Quy hoạch động nào, ta áp dụng khung 7 thành phần logic chuẩn mực:

1. State Definition & Invariant (Định nghĩa Trạng thái & Bất biến): $dp[i]$ đại diện chính xác $100\%$ cho đại lượng nào? (Là giá trị tối ưu, số cách thực hiện, hay trạng thái logic?).
2. Base Cases (Trường hợp cơ sở): Các trạng thái biên nhỏ nhất không thể phân rã thêm ($i = 0, 1$) có giá trị bằng bao nhiêu?
3. State Transition (Hệ thức chuyển trạng thái): Trạng thái $dp[i]$ phụ thuộc vào các trạng thái con dp[j] ($j < i$) nào trước đó qua công thức toán học nào?
4. Evaluation Order (Thứ tự tính toán): Chiều duyệt vòng lặp ($i = 1 \to N$ xuôi hay ngược) theo thứ tự Topo DAG để đảm bảo mọi bài toán con phụ thuộc đều đã được tính xong trước khi dùng.
5. Answer Extraction (Trích xuất kết quả): Đáp án của bài toán gốc nằm ở đâu? (Tại dp[N], hay $\max_{i=1}^N dp[i]$?).
6. Space & Time Optimization (Tối ưu hóa): Phân tích độ phức tạp thời gian $\mathcal{O}(\text{Time})$, bộ nhớ $\mathcal{O}(\text{Space})$ và khả năng nén mảng.
7. Reconstruction (Khôi phục nghiệm): Dùng mảng truy vết trace[i] hoặc duyệt ngược trên bảng dp để tái tạo lại cấu hình nghiệm tối ưu (Ghi N/A nếu bài toán chỉ yêu cầu giá trị).

3. Các mô hình quy hoạch động 1D cốt lõi (core patterns)

3.1. Mô hình bậc thang & bước nhảy (staircase / frog jump)

• Bối cảnh: Một chú ếch đứng ở bậc $0$, muốn nhảy lên bậc $N$. Tại mỗi bậc, ếch có thể nhảy $1$ bước hoặc $2$ bước.
• State Definition: $dp[i]$ là số cách khác nhau để ếch nhảy từ bậc $0$ đến bậc $i$.
• Base Cases: dp[0] = 1 (có đúng một cách để hoàn thành hành trình từ bậc 0 đến bậc 0 — không thực hiện bước nhảy nào), dp[1] = 1.

• State Transition: Để đến bậc $i$, bước nhảy cuối cùng bắt buộc phải xuất phát từ bậc $i-1$ (nhảy 1 bước) hoặc bậc $i-2$ (nhảy 2 bước): $$dp[i] = dp[i-1] + dp[i-2] \pmod{10^9+7}$$

• Evaluation Order: Duyệt xuôi từ $i = 2 \to N$.

3.2. Mô hình đổi tiền ít xu nhất (coin change 1D)

• Bối cảnh: Cho hệ thống gồm $K$ đồng xu có mệnh giá $C = \{c_1, c_2, \dots, c_K\}$. Cần đổi số tiền $S$ sao cho tổng số đồng xu là ít nhất.
• State Definition: $dp[i]$ là số lượng đồng xu ít nhất để tạo ra đúng tổng giá trị $i$.
• Base Cases: dp[0] = 0 (Tổng tiền bằng 0 cần đúng 0 đồng xu). Khởi tạo mọi dp[i] = \infty với $i \ge 1$.

• State Transition: Thử chọn đồng xu cuối cùng là mệnh giá $c \in C$: $$dp[i] = 1 + \min_{\{c \in C \mid i \ge c\}} dp[i - c]$$

• Evaluation Order: Duyệt xuôi $i = 1 \to S$. Nếu $dp[S] = \infty \implies$ Không thể đổi được.

Lưu ý quan trọng: Quy tắc thứ tự vòng lặp phân biệt Hoán vị / Tổ hợp dưới đây áp dụng cho bài toán đếm số cách. Với bài toán tối ưu số đồng xu ít nhất $dp[i] = 1 + \min(dp[i-c])$, do phép toán $\min$ có tính chất giao hoán và kết hợp nên ta luôn duyệt $i$ từ $1 \to S$ mà không làm thay đổi giá trị tối ưu.

• Phân biệt Sư phạm Cốt lõi Trong Bài Toán Đếm Số Cách (Counting Coin Change):
• Bài toán Hoán vị (Permutation): Thứ tự các đồng xu có phân biệt (ví dụ $1+2 \neq 2+1$ (khác $2+1$)). Vòng lặp ngoài duyệt Tiền $i = 1 \to S$, vòng lặp trong thử từng đồng xu $c \in C$.
• Bài toán Tổ hợp (Combination): Thứ tự các đồng xu không phân biệt (ví dụ $1+2$ và $2+1$ là một cách). Vòng lặp ngoài duyệt từng đồng xu $c \in C$, vòng lặp trong duyệt Tiền $i = c \to S$.

3.3. Dãy con tăng dài nhất (longest increasing subsequence — LIS $\mathcal{O}(N^2)$)

• Bối cảnh: Cho dãy số $A = [a_1, a_2, \dots, a_N]$. Tìm độ dài dãy con tăng nghiêm ngặt dài nhất.
• State Definition (Tử huyệt định nghĩa): $dp[i]$ là độ dài của dãy con tăng dài nhất kết thúc bắt buộc tại phần tử $A[i]$.
• Base Cases: dp[i] = 1 với mọi $1 \le i \le N$ (bản thân mỗi phần tử đơn lẻ là dãy con độ dài 1).

• State Transition: Duyệt qua mọi phần tử $A[j]$ đứng trước $A[i]$ ($1 \le j < i$): $$dp[i] = 1 + \max_{\{1 \le j < i \mid A[j] < A[i]\}} dp[j]$$

• Answer Extraction: Kết quả toàn cục là $\max_{i=1}^N dp[i]$.

• Độ phức tạp: $\mathcal{O}(N^2)$ thời gian, $\mathcal{O}(N)$ bộ nhớ. Thường phù hợp với $N$ cỡ vài nghìn, tùy thuộc vào time limit và hệ số hằng số.

3.4. Kỹ thuật khôi phục vết nghiệm 1D (traceback / reconstruction)

Để in ra chính xác cấu hình dãy phần tử tạo nên nghiệm tối ưu:

1. Duy trì mảng trace[i] = j ghi nhận chỉ số phần tử đứng ngay trước $A[i]$ trong cấu hình tối ưu.
2. Tìm vị trí $best\_idx$ có $dp[best\_idx]$ đạt cực trị.
3. Lần ngược mảng trace từ $best\_idx$ về điểm xuất phát, lưu các phần tử vào một vector rồi đảo ngược (reverse).

3.5. Mở rộng nâng cao: LIS $\mathcal{O}(N \log N)$ bằng Binary Search

Khi $N \le 10^5$, thuật toán $\mathcal{O}(N^2)$ sẽ bị Quá thời gian (TLE).

• Ý tưởng: Duy trì mảng phụ tails trong C++ (chỉ số 0-based), trong đó phần tử $tails[len - 1]$ lưu giá trị phần tử kết thúc nhỏ nhất của một dãy con tăng có độ dài đúng bằng len.
• Mảng $tails$ luôn có tính chất đơn điệu tăng dần $\implies$ Dùng Tìm kiếm nhị phân (lower_bound) để tìm và cập nhật vị trí thích hợp cho mỗi $A[i]$ trong $\mathcal{O}(\log N)$.
• Tổng thời gian: $\mathcal{O}(N \log N)$. Đây là kỹ thuật mở rộng tối ưu hóa nâng cao (Challenge Extension).

4. Các biến thể thiết kế trạng thái từ mô hình 1D (state design variations)

Mục tiêu lớn nhất của Module 05 không phải là học thuộc các công thức, mà là rèn luyện khả năng Thiết Kế Trạng Thái (State Design) trước các biến thể bài toán mới:

4.1. Pattern a: Quyết định nhị phân (binary choice — Chọn / bỏ qua)

• Bối cảnh (House Robber): Không được chọn hai phần tử liền kề nhau.
• State Invariant: $dp[i]$ là tổng giá trị lớn nhất khi chỉ xét tiền tố từ $1 \dots i$.

• Transition: Tại vị trí $i$, có 2 lựa chọn loại trừ lẫn nhau: $$dp[i] = \max(\underbrace{dp[i-1]}_{\text{Không chọn } i}, \underbrace{dp[i-2] + A[i]}_{\text{Chọn } i \implies \text{bỏ qua } i-1})$$

• Chuyển đổi bài toán (Delete and Earn): Khi chọn giá trị $v$, ta nhận toàn bộ tổng điểm $points[v] = v \times count(v)$ nhưng bị cấm chọn $v-1$ và $v+1$. Bằng cách gom nhóm dữ liệu theo trục giá trị $v$, bài toán được quy đổi hoàn toàn về mô hình House Robber trên mảng $points$.

4.2. Pattern b: Mở rộng trạng thái hữu hạn (state dimension expansion)

• Bối cảnh (Alternating Subsequence): Dãy con đan dấu (tăng $\to$ giảm $\to$ tăng $\to$ giảm).
• Vấn đề: Nếu chỉ dùng $dp[i]$, ta không biết phần tử $A[i]$ đang đóng vai trò là "đỉnh tăng" hay "đáy giảm".
• Thiết kế Trạng thái: Bổ sung thêm một chiều trạng thái hữu hạn $\text{state} \in \{0, 1\}$:

• dp[i][0]: Độ dài dãy đan dấu kết thúc tại $A[i]$ với bước nhảy cuối cùng là GIẢM ($A[j] > A[i]$).

• dp[i][1]: Độ dài dãy đan dấu kết thúc tại $A[i]$ với bước nhảy cuối cùng là TĂNG ($A[j] < A[i]$).

• Lưu ý: Chiều bắt đầu của dãy con có thể linh hoạt bắt đầu bằng tăng hoặc giảm tùy theo yêu cầu đề bài; kết quả toàn cục thường là $\max(\max_i dp[i][0], \max_i dp[i][1])$.

• Lưu ý: Với dãy có độ dài 1, chưa tồn tại bước nhảy tăng/giảm; giá trị khởi tạo cụ thể của dp[i][0], dp[i][1] phụ thuộc vào định nghĩa bài toán và cách triển khai. Phần này được xem như mô hình mở rộng, không phải template cài đặt đầy đủ trong chuyên đề này.

4.3. Pattern c: Thay đổi đại lượng tối ưu (maximum sum increasing subsequence — Msis)

• Bối cảnh: Thay vì tìm dãy con tăng có độ dài lớn nhất, bài toán yêu cầu tìm dãy con tăng có tổng giá trị các phần tử lớn nhất.
• Điều chỉnh Invariant:
• LIS: $dp[i]$ = độ dài LIS $\implies dp[i] = 1 + \max(dp[j])$.
• MSIS: $dp[i]$ = Tổng lớn nhất của dãy con tăng kết thúc tại $A[i]$: $$dp[i] = A[i] + \max_{\{j < i \mid A[j] < A[i]\}} dp[j]$$

4.4. Pattern d: Phân hoạch đoạn tối ưu (pattern mở rộng / preview — Optimal array partitioning & rod cutting)

• Bối cảnh: Cắt một thanh gỗ độ dài $N$ (hoặc phân chia dãy số $A[1 \dots N]$ thành các đoạn con liên tiếp) sao cho tổng giá trị/chi phí là tối ưu.
• State Invariant: $dp[i]$ là chi phí/giá trị tối ưu khi phân hoạch tiền tố $A[1 \dots i]$.

• Transition: Thử mọi điểm cắt cuối cùng $j \in [0, i-1]$: $$dp[i] = \min_{0 \le j < i, \text{valid}(j+1, i)} (dp[j] + \text{cost}(j+1, i))$$

• Áp dụng cho bài Mastery CPPB-DP1-15: Tìm cách phân chia dãy số thành các khối đoạn con thỏa mãn điều kiện ràng buộc với chi phí nhỏ nhất.

5. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy khởi tạo giá trị vô cùng (Infinity Overflow): * Khi tìm giá trị nhỏ nhất, nếu dùng INT_MAX cho kiểu int, phép tính dp[i-c] + 1 sẽ gây tràn số thành số âm cực lớn. * Quy tắc an toàn: Dùng hằng số const long long INF = 1e18; (hoặc 1LL << 60) và luôn kiểm tra if (dp[i - c] != INF) trước khi chuyển trạng thái.
2. Bẫy định nghĩa sai Trạng thái trong LIS: * Ngộ nhận: "dp[i] là độ dài LIS trong đoạn từ 1 đến i". Nếu định nghĩa như vậy, ta không thể biết phần tử kết thúc là bao nhiêu để so sánh với $A[i+1]$. * Bất biến đúng: Bắt buộc $dp[i]$ phải là độ dài LIS kết thúc tại chính $A[i]$.
3. Bẫy nhầm lẫn thứ tự vòng lặp trong Coin Change Đếm Số Cách: * Duyệt Tiền trước, Coin sau $\implies$ Tạo ra bài toán Hoán vị (đếm lặp thứ tự). * Duyệt Coin trước, Tiền sau $\implies$ Tạo ra bài toán Tổ hợp (đếm không trùng lặp).

6. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1: Dãy con tăng dài nhất LIS $\mathcal{O}(N^2)$ kèm truy vết nghiệm

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    if (n <= 0) return 0;

    vector<long long> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];

    }

    vector<int> dp(n, 1);

    vector<int> trace(n, -1);

    int max_len = 1;
    int best_end = 0;

    // Quy hoạch động O(N^2)
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {

                dp[i] = dp[j] + 1;
                trace[i] = j;
            }
        }
        if (dp[i] > max_len) {

            max_len = dp[i];
            best_end = i;
        }
    }

    cout << max_len << "\n";

    // Khôi phục vết nghiệm
    vector<long long> lis_elements;

    int curr = best_end;
    while (curr != -1) {
        lis_elements.push_back(a[curr]);
        curr = trace[curr];
    }
    reverse(lis_elements.begin(), lis_elements.end());

    for (int i = 0; i < (int)lis_elements.size(); ++i) {
        cout << lis_elements[i] << (i + 1 == (int)lis_elements.size() ? "" : " ");
    }
    cout << "\n";

    return 0;
}

Mẫu 2: Đổi tiền ít xu nhất (coin change 1D)

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

const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    long long s;
    if (!(cin >> k >> s)) return 0;

    vector<long long> c(k);

    for (int i = 0; i < k; ++i) {
        cin >> c[i];

    }

    vector<long long> dp(s + 1, INF);

    dp[0] = 0;

    for (int i = 1; i <= s; ++i) {
        for (long long coin : c) {
            if (i >= coin && dp[i - coin] != INF) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    if (dp[s] == INF) {
        cout << -1 << "\n";
    } else {
        cout << dp[s] << "\n";
    }

    return 0;
}