Trang chủ Bài tập Kỳ thi Bài nộp Xếp hạng Thảo luận Trợ giúp
Đăng nhập Đăng ký
Thảo luận
Khu vực thảo luận

CHUYÊN ĐỀ QUY HOẠCH ĐỘNG

Trùm CUỐI 2025-06-24 12:36:19

Mục tiêu:

  • Hiểu rõ triết lý cốt lõi của Quy hoạch động: giải các bài toán con chồng chéo và cấu trúc con tối ưu.
  • Nắm vững quy trình 4 bước để giải một bài toán DP: định nghĩa trạng thái, tìm công thức chuyển trạng thái, xác định trạng thái cơ sở, và truy vết kết quả.
  • Thành thạo các dạng DP kinh điển và nhận diện được chúng trong các bài toán mới.
  • Phát triển kỹ năng tối ưu hóa DP, từ tối ưu không gian đến sử dụng các cấu trúc dữ liệu.

NỘI DUNG CHI TIẾT

Lời Mở Đầu: DP là gì và tại sao lại "khó"?

Quy hoạch động (Dynamic Programming - DP) thường bị coi là một trong những chủ đề "khó nhằn" nhất trong lập trình thi đấu. Lý do không phải vì nó là một thuật toán phức tạp, mà vì nó là một phương pháp tư duy, một cách tiếp cận để giải quyết vấn đề. DP không có một công thức chung áp dụng cho mọi bài toán; thay vào đó, nó đòi hỏi khả năng nhận diện cấu trúc và xây dựng một lời giải tối ưu từ những mảnh ghép nhỏ hơn.

  • Câu chuyện mở đầu: Bài toán Fibonacci

Để hiểu rõ sức mạnh của DP, hãy xét bài toán kinh điển: tính số Fibonacci thứ n .

  • Cách giải đệ quy thông thường: Định nghĩa toán học của dãy Fibonacci là fib(n) = fib(n-1) + fib(n-2) , với fib(0)=0, fib(1)=1 . Một cách tự nhiên, ta có thể viết hàm đệ quy sau:

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

    Hãy xem cây gọi đệ quy cho fib(5):

    Ta thấy fib(3) được tính 2 lần, fib(2) được tính 3 lần,... Đây là sự lãng phí tính toán khổng lồ. Vấn đề này được gọi là bài toán con chồng chéo (overlapping subproblems).

  • Cách giải tối ưu (Ghi nhớ - Memoization): Để tránh tính toán lại, ta có thể lưu kết quả của các bài toán con đã giải vào một mảng. Đây chính là kỹ thuật ghi nhớ.

    int memo[100]; // Khởi tạo mảng với giá trị -1

int fib_memo(int n) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != -1) { // Nếu đã tính, trả về kết quả đã lưu
        return memo[n];
    }
    // Nếu chưa tính, tính toán và lưu lại
    memo[n] = fib_memo(n-1) + fib_memo(n-2);
    return memo[n];
}

    Với cách này, mỗi giá trị fib(i) chỉ được tính đúng một lần.

  • Cách giải không đệ quy (Bottom-up): Ta có thể khử hoàn toàn đệ quy bằng cách tính các giá trị Fibonacci tuần tự từ dưới lên. Ta biết rằng để tính fib(n), ta cần fib(n-1) và fib(n-2). Vậy hãy tính fib(2), fib(3), ... cho đến fib(n).

    int fib_bottom_up(int n) {
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

    Cách tiếp cận này hoạt động được vì lời giải của bài toán lớn (fib(n)) được xây dựng từ lời giải tối ưu của các bài toán con (fib(n-1) và fib(n-2)). Tính chất này được gọi là cấu trúc con tối ưu (optimal substructure).

  • Kết luận: DP không phải là một thuật toán, mà là một phương pháp tư duy, một kỹ thuật tối ưu hóa các bài toán đệ quy có hai tính chất trên bằng cách ghi nhớ kết quả.

Phần I: Nền Tảng và Quy Trình Tư Duy DP

Mục tiêu: Xây dựng một "framework" vững chắc để tiếp cận bất kỳ bài toán DP nào.

  1. Hai Tính Chất Cốt Lõi:

    • Overlapping Subproblems (Bài toán con chồng chéo): Một bài toán có thể được chia thành các bài toán con nhỏ hơn, và các bài toán con này được giải lặp đi lặp lại nhiều lần. DP giải quyết vấn đề này bằng cách lưu trữ kết quả của mỗi bài toán con để sử dụng lại.
    • Optimal Substructure (Cấu trúc con tối ưu): Lời giải tối ưu của bài toán lớn có thể được xây dựng từ lời giải tối ưu của các bài toán con của nó. Đây là điều kiện tiên quyết để có thể áp dụng DP.

  2. Hai Cách Tiếp Cận Cài Đặt:

    • Top-down (Memoization):

      • Tư tưởng: Bắt đầu từ bài toán lớn (top), dùng đệ quy để chia thành các bài toán con. Nếu một bài toán con đã được giải, lấy kết quả đã lưu. Nếu chưa, giải nó và lưu kết quả trước khi trả về.
      • Ưu điểm: Gần với suy nghĩ tự nhiên, dễ cài đặt từ công thức đệ quy. Chỉ tính các trạng thái cần thiết.
      • Nhược điểm: Có chi phí của các lời gọi hàm đệ quy (overhead), có thể gây tràn bộ nhớ stack nếu độ sâu đệ quy quá lớn.

    • Bottom-up (Tabulation):

      • Tư tưởng: Xây dựng một bảng (thường là mảng) và điền các giá trị của bài toán con từ nhỏ nhất đến lớn nhất (bottom-up). Lời giải của bài toán sau được tính dựa trên các kết quả đã có sẵn trong bảng.
      • Ưu điểm: Không có overhead của đệ quy, thường nhanh hơn một chút. Không có nguy cơ tràn bộ nhớ stack.
      • Nhược điểm: Cần xác định thứ tự tính toán chính xác. Có thể tính cả những trạng thái không cần thiết cho kết quả cuối cùng.

    Khuyến nghị: Hãy tập tư duy theo kiểu Top-down để tìm ra công thức truy hồi, sau đó cài đặt bằng Bottom-up để đạt hiệu suất tốt nhất và tránh các vấn đề về đệ quy.

  3. Quy Trình 4 Bước Vàng: Đây là "kim chỉ nam" để giải quyết một bài toán DP.

    • Bước 1: Định nghĩa Trạng thái (State):

      • Đây là bước khó và quan trọng nhất. Bạn phải xác định các tham số có thể mô tả một bài toán con một cách duy nhất.
      • dp[i], dp[i][j], dp[mask],... là gì? Nó biểu diễn giá trị tối ưu (tổng lớn nhất, chi phí nhỏ nhất, số cách,...) của bài toán con nào?
      • Ví dụ: dp[i] là "độ dài dãy con tăng dài nhất kết thúc tại vị trí i".

    • Bước 2: Tìm Công thức Chuyển Trạng thái (Transition):

      • Làm thế nào để tính trạng thái hiện tại từ các trạng thái nhỏ hơn đã được tính? Đây chính là trái tim của thuật toán DP.
      • Công thức này thể hiện mối quan hệ giữa các bài toán con, hay chính là phần "cấu trúc con tối ưu".
      • Ví dụ: Để tính dp[i], ta xét tất cả các j < i. Nếu a[j] < a[i], ta có thể kéo dài dãy con kết thúc tại j. Vậy dp[i] = 1 + max(dp[j]).

    • Bước 3: Xác định Trạng thái Cơ sở (Base Case):

      • Đây là những trạng thái nhỏ nhất mà ta biết trước lời giải mà không cần tính toán phức tạp. Nó là điểm bắt đầu của quá trình DP.
      • Ví dụ: dp[0] = 1 (dãy con tăng dài nhất kết thúc ở phần tử đầu tiên có độ dài là 1).

    • Bước 4 (Tùy chọn): Truy vết (Path Reconstruction):

      • Nhiều bài toán không chỉ yêu cầu giá trị tối ưu (ví dụ: độ dài 5) mà còn yêu cầu chính lời giải đó (dãy con đó là gì?).
      • Để truy vết, ta thường lưu lại "lựa chọn" đã dẫn đến kết quả tối ưu tại mỗi bước. Sau khi tính xong bảng DP, ta đi ngược từ trạng thái cuối cùng về trạng thái cơ sở để xây dựng lại lời giải.

Phần II: Các Dạng DP Kinh Điển (Classical Problems)

Nắm vững các bài toán này là nền tảng để giải quyết các vấn đề phức tạp hơn.

A. Dãy con tăng dài nhất (Longest Increasing Subsequence - LIS)

  • Bài toán: Cho một dãy số A gồm N phần tử. Tìm độ dài của dãy con (không nhất thiết liên tiếp) dài nhất có các phần tử tăng dần.

  • Lời giải O(N^2) :

    • State: dp[i] là độ dài của dãy con tăng dài nhất kết thúc tại vị trí i.
    • Transition: Để tính dp[i], ta có thể tạo ra một dãy con tăng mới chỉ có a[i] (dài 1), hoặc mở rộng một dãy con tăng đã có. Ta tìm tất cả các vị trí j < i mà a[j] < a[i]. Với mỗi j như vậy, ta có thể thêm a[i] vào sau dãy con kết thúc tại j.

      dp[i] = 1 + \max(\{dp[j] \mid 0 \le j < i \text{ và } a[j] < a[i]\} \cup \{0\})

    • Base Case: dp[i] = 1 với mọi i (vì mỗi phần tử tự nó là một dãy con tăng dài 1).
    • Kết quả: \max(dp[0], dp[1], ..., dp[N-1]) .

  • Lời giải O(N \log N) (Tối ưu hóa):

    • Tư tưởng: Thay vì hỏi "độ dài LIS kết thúc tại i là bao nhiêu?", ta hỏi "phần tử cuối cùng nhỏ nhất của một LIS có độ dài k là gì?".
    • Cách tiếp cận: Duy trì một mảng tail[] sao cho tail[k] là phần tử cuối cùng nhỏ nhất có thể có của một dãy con tăng có độ dài k+1.
    • Khi xét phần tử a[i]:
      1. Nếu a[i] lớn hơn tất cả các phần tử trong tail (tức là lớn hơn tail[len-1]), ta có thể mở rộng LIS dài nhất hiện tại. Ta thêm a[i] vào cuối tail và tăng len.
      2. Nếu a[i] không lớn hơn, ta tìm vị trí k trong tail sao cho tail[k] là phần tử đầu tiên lớn hơn hoặc bằng a[i]. Ta thay thế tail[k] bằng a[i]. Điều này có nghĩa là ta đã tìm ra một cách tốt hơn để tạo ra một dãy con tăng có độ dài k+1 (với phần tử cuối cùng nhỏ hơn).
    • Việc tìm kiếm vị trí k có thể được thực hiện hiệu quả bằng tìm kiếm nhị phân (binary search), đưa độ phức tạp mỗi bước xuống O(\log N) .

B. Dãy con chung dài nhất (Longest Common Subsequence - LCS)

  • Bài toán: Cho hai chuỗi S1 và S2 . Tìm độ dài của dãy con chung dài nhất của chúng.

  • Lời giải O(N \times M) :

    • State: dp[i][j] là độ dài LCS của chuỗi con S1[1...i] và S2[1...j].
    • Transition: Khi tính dp[i][j], ta xét hai ký tự S1[i] và S2[j]:
      • Nếu S1[i] == S2[j]: Ký tự này là một phần của LCS. Ta có thể kéo dài LCS của S1[1...i-1] và S2[1...j-1].

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

      • Nếu S1[i] != S2[j]: Ký tự chung không thể bao gồm cả hai. Ta phải bỏ một trong hai. Lời giải tối ưu sẽ là lời giải tốt nhất khi bỏ S1[i] hoặc bỏ S2[j].

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

    • Base Case: dp[0][j] = 0 và dp[i][0] = 0 cho mọi i, j.
    • Kết quả: dp[length(S1)][length(S2)].

  • Ứng dụng: Khoảng cách chỉnh sửa (Edit Distance) Bài toán Edit Distance yêu cầu tìm số phép biến đổi ít nhất (thêm, xóa, thay thế) để biến chuỗi S1 thành S2. Công thức DP rất tương tự LCS, chỉ khác ở cách xử lý.

C. Bài toán cái túi (Knapsack)

  • 0/1 Knapsack: Cho N vật, mỗi vật có trọng lượng weight[i] và giá trị value[i]. Cho một cái túi có sức chứa tối đa là W. Chọn một số vật (mỗi vật chỉ có thể chọn 1 lần hoặc không) sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất.

    • State: dp[i][w] là giá trị lớn nhất có thể đạt được khi xét i vật đầu tiên với giới hạn trọng lượng là w.
    • Transition: Khi xét vật thứ i, ta có hai lựa chọn:
      1. Không chọn vật i: Giá trị tối ưu sẽ giống như khi xét i-1 vật với cùng trọng lượng w. Tức là dp[i-1][w].
      2. Chọn vật i (nếu có thể): Nếu w >= weight[i], ta có thể chọn nó. Giá trị sẽ là value[i] cộng với giá trị tối ưu có thể đạt được với i-1 vật còn lại và trọng lượng còn lại là w - weight[i]. Tức là value[i] + dp[i-1][w - weight[i]].

        dp[i][w] = \max(dp[i-1][w], \quad value[i] + dp[i-1][w - weight[i]])

    • Base Case: dp[0][w] = 0 cho mọi w.

  • Unbounded Knapsack: Tương tự 0/1 Knapsack, nhưng mỗi vật có thể được chọn nhiều lần.

    • State: Tương tự.
    • Transition: Công thức chuyển trạng thái có một thay đổi nhỏ. Khi chọn vật i, ta vẫn có thể tiếp tục chọn vật i nữa.

      dp[i][w] = \max(dp[i-1][w], \quad value[i] + dp[i][w - weight[i]])

      Sự khác biệt nằm ở dp[i] thay vì dp[i-1] trong vế thứ hai, cho phép tái sử dụng vật i.

Phần III: Các Dạng DP Phổ Biến (Common Patterns)

Mục tiêu: Mở rộng khả năng áp dụng DP vào các cấu trúc khác nhau.

A. DP trên Đoạn/Khoảng (Interval DP)

  • Dấu hiệu: Bài toán yêu cầu tối ưu một giá trị nào đó trên một đoạn [i, j]. Lời giải của đoạn lớn được xây dựng từ các đoạn con bên trong nó.
  • State: dp[i][j] là kết quả tối ưu cho đoạn từ i đến j.
  • Transition: Vòng lặp for thường duyệt qua độ dài của đoạn len, rồi duyệt qua điểm bắt đầu i. Điểm kết thúc j sẽ là i + len - 1. Công thức chuyển trạng thái thường duyệt qua một điểm chia k (i <= k < j) để chia đoạn [i, j] thành hai đoạn con [i, k] và [k+1, j].

    dp[i][j] = \min_{i \le k < j} / \max_{i \le k < j} (dp[i][k] + dp[k+1][j] + \text{cost}(i, k, j))

    cost(i, k, j) là chi phí để kết hợp hai đoạn con.
  • Bài toán kinh điển: Nhân ma trận (Matrix Chain Multiplication), Đóng ngoặc biểu thức để được giá trị lớn nhất/nhỏ nhất.

B. DP trên Lưới (Grid DP)

  • Dấu hiệu: Bài toán cho trên một bảng 2 chiều (lưới), thường yêu cầu di chuyển từ một ô này sang ô khác theo những quy tắc nhất định (ví dụ: chỉ sang phải hoặc xuống dưới).
  • State: dp[i][j] là kết quả tối ưu (số cách, tổng lớn nhất,...) khi đi đến ô (i, j).
  • Transition: Kết quả tại dp[i][j] được tính dựa trên các ô có thể đi đến nó. Nếu chỉ được đi từ ô bên trên (i-1, j) và ô bên trái (i, j-1), công thức sẽ là:

    dp[i][j] = dp[i-1][j] + dp[i][j-1] \quad (\text{cho bài toán đếm đường đi})

    dp[i][j] = \text{value}[i][j] + \max(dp[i-1][j], dp[i][j-1]) \quad (\text{cho bài toán tìm đường đi có tổng lớn nhất})

  • Bài toán kinh điển: Đếm số đường đi trong lưới, Tìm đường đi có tổng lớn nhất/nhỏ nhất.

C. DP trên Cây (DP on Trees)

  • Dấu hiệu: Bài toán yêu cầu tìm một giá trị tối ưu trên một cấu trúc cây.
  • Tư tưởng: Dùng thuật toán duyệt theo chiều sâu (DFS). Khi DFS đi xuống đến các nút lá, nó bắt đầu tính toán và trả kết quả ngược lên cho các nút cha. Kết quả của một nút u được tính dựa trên kết quả đã tính của các nút con của nó.
  • State: Thường có dạng dp[u][state], trong đó u là nút đang xét và state là một trạng thái của nút u.
    • Ví dụ: Tìm tập độc lập lớn nhất (Maximum Independent Set). Một tập hợp các đỉnh được gọi là độc lập nếu không có hai đỉnh nào kề nhau.
    • State:
      • dp[u][0]: Kích thước tập độc lập lớn nhất trong cây con gốc u, với điều kiện nút u không được chọn.
      • dp[u][1]: Kích thước tập độc lập lớn nhất trong cây con gốc u, với điều kiện nút u được chọn.
    • Transition (với v là con của u):
      • Nếu u không được chọn (dp[u][0]), các con v của nó có thể được chọn hoặc không. Ta lấy phương án tốt nhất cho mỗi con:

      dp[u][0] = \sum_{v \in \text{children}(u)} \max(dp[v][0], dp[v][1])

      • Nếu u được chọn (dp[u][1]), tất cả các con v của nó đều không được chọn:

      dp[u][1] = 1 + \sum_{v \in \text{children}(u)} dp[v][0]

  • Bài toán kinh điển: Tìm tập độc lập lớn nhất (Maximum Independent Set), Tìm đường kính cây (đường đi dài nhất trong cây), Vertex Cover.

D. DP Trạng thái Bitmask (Bitmask DP)

  • Dấu hiệu: Ràng buộc của N rất nhỏ (thường N \le 20 hoặc N \le 22 ). Bài toán liên quan đến việc sử dụng/phân chia/ghép cặp một tập hợp các phần tử, trong đó trạng thái "đã dùng" hay "chưa dùng" của mỗi phần tử là quan trọng.
  • Tư tưởng: Dùng một số nguyên (bitmask) để biểu diễn trạng thái của một tập hợp. Bit thứ i trong mask bật (bằng 1) có nghĩa là phần tử thứ i đã được sử dụng/chọn, và ngược lại nếu bit tắt (bằng 0).
  • State: dp[mask] là kết quả tối ưu cho tập hợp các phần tử được biểu diễn bởi mask.
  • Transition: Thường duyệt qua tất cả các mask từ 0 đến 2^N - 1 . Để tính dp[mask], ta có thể:
    • Duyệt qua các "trạng thái con" của mask.
    • Duyệt qua từng phần tử i trong mask và thử loại bỏ nó, chuyển từ trạng thái mask \setminus \{i\} (tức là mask XOR 1 << i).
  • Bài toán kinh điển: Người du lịch (Traveling Salesperson Problem - TSP) với N \le 20 .
    • State: dp[mask][i] là chi phí nhỏ nhất để đi thăm các thành phố trong mask, kết thúc tại thành phố i.
    • Transition:

      dp[\text{mask}][i] = \min_{j \in \text{mask}, j \ne i} (dp[\text{mask} \oplus (1 \ll i)][j] + \text{cost}[j][i])

      Điều này có nghĩa là, để đến i với tập mask, ta đã phải đến một thành phố j nào đó trước đó với tập mask chưa bao gồm i.

Phần IV: Kỹ Năng Tối Ưu Hóa DP

  • Tối ưu không gian (Space Optimization):

    • Trong nhiều bài toán DP (như Knapsack, LCS), để tính hàng i của bảng DP, ta chỉ cần thông tin từ hàng i-1 (hoặc một vài hàng ngay trước đó). Ta không cần lưu toàn bộ bảng.
    • Ví dụ (0/1 Knapsack): Thay vì dùng dp[i][w], ta có thể dùng một mảng 1 chiều dp[w].
      // Thay vì dp[N+1][W+1]
int dp[W+1]; 

for (int i = 1; i <= N; i++) {
    // Duyệt ngược để không dùng một vật nhiều lần trong cùng một bước
    for (int w = W; w >= weight[i]; w--) { 
        dp[w] = max(dp[w], value[i] + dp[w - weight[i]]);
    }
}
    • Kỹ thuật này giảm không gian từ O(N \times W) xuống O(W) .

  • Sử dụng Cấu trúc dữ liệu:

    • Đôi khi, bước chuyển trạng thái yêu cầu tìm một giá trị min/max/sum trên một khoảng nào đó (ví dụ LIS O(N^2) ). Việc này có thể được tăng tốc bằng các cấu trúc dữ liệu như Segment Tree hoặc Fenwick Tree (BIT).
    • Ví dụ: LIS O(N \log N) thực chất là một dạng tối ưu hóa. Mảng tail và tìm kiếm nhị phân đóng vai trò như một cấu trúc dữ liệu giúp tìm kiếm vị trí cần cập nhật một cách hiệu quả. Một cách cài đặt khác cho LIS O(N \log N) là nén số và dùng Segment Tree/BIT để tìm max(dp[j]) trong O(\log N) .

  • Convex Hull Trick / DP SOS (Sum over Subsets):

    • Convex Hull Trick: Một kỹ thuật tối ưu hóa nâng cao dành cho các bài DP có công thức chuyển trạng thái dạng tuyến tính:

      dp[i] = \min_{0 \le j < i} (dp[j] + b[j] \times a[i])

      Kỹ thuật này duy trì một tập hợp các đường thẳng và truy vấn giá trị nhỏ nhất tại một điểm một cách hiệu quả, thường trong O(\log N) hoặc O(1) (nếu các hệ số góc có thứ tự).
    • Sum over Subsets (SOS) DP: Một kỹ thuật dùng để tính toán nhanh các tổng trên tất cả các tập con (submask) của các bitmask. Với một mảng A[mask], ta muốn tính một mảng F[mask] = \sum_{sub \subseteq mask} A[sub] . SOS DP có thể tính tất cả các giá trị này trong O(N \cdot 2^N) .

Phần V: Bài Tập Luyện Tập

  • Level 1 (Kinh điển):

    • Cài đặt lại các bài toán LIS, LCS, 0/1 Knapsack, Unbounded Knapsack.
    • Các bài Grid DP cơ bản: Đếm đường đi, đường đi có tổng lớn nhất.
    • (AtCoder DP Contest: A, B, C, D, E)

  • Level 2 (Nhận diện):

    • Các bài toán biến thể của các dạng kinh điển.
    • Các bài DP trên đoạn (Matrix Chain Multiplication).
    • Các bài DP trên cây cơ bản (Maximum Independent Set).
    • (CSES DP Section: Removing Digits, Minimizing Coins, Coin Combinations I & II, Grid Paths)
    • (AtCoder DP Contest: F, G, H, I)

  • Level 3 (Bitmask & Tối ưu):

    • Các bài toán với N nhỏ đòi hỏi Bitmask DP (CSES: Counting Tilings, Hamiltonia Flights; AtCoder DP Contest: O).
    • Các bài toán yêu cầu tối ưu không gian hoặc tối ưu công thức chuyển trạng thái bằng cấu trúc dữ liệu.
    • (CSES DP Section: Projects, Elevator Rides)
    • (AtCoder DP Contest: Các bài còn lại)

  • Nguồn bài tập chất lượng:

Chuyên Sơn La Online Judge.
Mã nguồn mở cho giải pháp chấm bài trực tuyến (Online Judge): DMOJ - UOJ - QDUOJ - SYZOJ - OJS - SHARIF - AURORA - CMS