cpp-096Bước 1Trung bình
Khoảng cách chỉnh sửa Levenshtein: Quy hoạch động tối ưu bộ nhớ 1D
Cho hai chuỗi ký tự A và B. Hãy tìm số thao tác ít nhất để biến đổi chuỗi A thành chuỗi B.
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Quy hoạch động (Dynamic Programming) trong C++
Quy hoạch động là linh hồn của các kỳ thi học sinh giỏi Tin học và lập trình thi đấu. Luyện tập phân rã bài toán, thiết lập công thức truy hồi và tối ưu độ phức tạp.
32
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
0
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
12
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
20
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Lộ trình thực hành đề xuất
Bước 1
DP 1 Chiều cơ bản
Các bài toán dãy số, bước nhảy, bài toán đổi tiền và mảng DP 1 chiều.
Bước 2
Dãy con tăng dài nhất (LIS)
Cài đặt LIS O(N²) và nâng cấp lên O(N log N) bằng tìm kiếm nhị phân.
Bước 3
Bài toán Cái ba lô (Knapsack)
Ba lô 0/1, ba lô vô hạn và kỹ thuật tối ưu mảng DP từ 2D xuống 1D.
Bước 4
Xâu con chung dài nhất (LCS)
Quy hoạch động trên xâu ký tự và truy vết chuỗi con chung.
Bước 5
DP Trạng thái (Bitmask DP)
Biểu diễn tập hợp con bằng bitmask để giải bài toán người du lịch TSP.
Lỗi thường gặp & Cách phòng tránh
•
Khởi tạo bảng DP bằng 0 thay vì giá trị vô cùng (-INF / +INF) trong bài toán tìm cực trị.
•
Duyệt ngược vòng lặp thể tích sai trong bài toán ba lô 0/1 làm một vật phẩm bị chọn nhiều lần.
Danh sách bài tập thực hành (32 bài)
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Trung bình 12 bài
Vận dụng
Dùng một kỹ thuật quen thuộc: sắp xếp, tìm kiếm, đếm, ngăn xếp.
cpp-275Bước 2Trung bình
Tổng đoạn con lớn nhất (thuật toán Kadane)
Tìm đoạn con liên tiếp có tổng lớn nhất dạy tư duy quy hoạch động: tại mỗi vị trí chỉ cần biết đoạn tốt nhất kết thúc ở đây. Kadane giải trong O(N) thay vì thử mọi đoạn O(N2).
cpp-133Bước 3Trung bình
Tam Giác Pascal và Đường Đi Có Tổng Lớn Nhất Trên Tam Giác Số
Cho một tam giác số gồm N hàng. Hàng thứ i (1 ≤ i ≤ N) có đúng i số nguyên.
cpp-158Bước 4Trung bình
Bài Toán Đổi Tiền Xu - Số Đồng Xu Tối Thiểu (Coin Change)
Bạn có N loại đồng xu có mệnh giá nguyên dương C1, C2, …, CN. Số lượng mỗi loại đồng xu là không giới hạn.
cpp-082Bước 5Trung bình
Thuật toán Kadane: Tổng đoạn con liên tiếp lớn nhất trên mảng vòng tròn
Cho một mảng gồm N số nguyên A1, A2, …, AN được xem như một vòng tròn khép kín. Hãy tìm một đoạn con liên tiếp không rỗng có tổng các phần tử lớn nhất.
cpp-156Bước 6Trung bình
Dãy Con Chung Dài Nhất Của 3 Chuỗi (LCS of Three Strings)
Cho ba chuỗi ký tự S1, S2, S3.
Kết hợp kỹ thuật
Phối hợp hai kỹ thuật trong cùng một lời giải.
cpp-157Bước 7Trung bình
Nhân Chuỗi Ma Trận Chi Phí Nhỏ Nhất (Matrix Chain Multiplication)
Cho một chuỗi gồm N ma trận A1, A2, …, AN. Ma trận Ai có kích thước Pi-1 × Pi.
cpp-155Bước 8Trung bình
Dãy Con Tăng Dài Nhất và Truy Vết Nghiệm (LIS with Path)
Cho một dãy gồm N số nguyên A1, A2, …, AN.
cpp-184Bước 9Trung bình
Tối ưu hóa quy hoạch động bằng hàng đợi đơn điệu (Monotonic Queue DP)
Có một dãy gồm N bậc thang được đánh số từ 1 đến N. Tại mỗi bậc thang i có một chi phí phạt là Ci (có thể âm, bằng 0, hoặc dương).
cpp-023Bước 10Trung bình
Quy hoạch động bài toán Cái túi 0/1 tối ưu không gian
Máy chủ huấn luyện đồ họa AI của AI Empire Academy có tổng dung lượng bộ nhớ VRAM là C GB (1 ≤ C ≤ 104). Có N mô hình AI mã nguồn mở đang được xem xét để nạp vào bộ nhớ (1…
cpp-027Bước 11Trung bình
Xâu con chung dài nhất (LCS) và truy vết khôi phục chuỗi
Trong hệ thống đối soát phiên bản mã nguồn của AI Empire Academy, công cụ diff cần tìm chuỗi chỉ thị chung dài nhất giữa hai bản thảo thuật toán để xác định phần mã không bị thay đ…
cpp-060Bước 12Trung bình
DP trên DAG: Đường đi Dài nhất và Đếm số Đường đi
Cho một đồ thị có hướng không có chu trình (DAG) gồm N đỉnh và M cạnh. Đỉnh xuất phát là 1 và đỉnh kết thúc là N. Hãy tính:
Nâng cao 20 bài
Thử thách
Thuật toán chuyên sâu: quy hoạch động, đồ thị, cây.
cpp-181Bước 1Nâng cao
Digit DP: Đếm số có tổng các chữ số chia hết cho K
Cho ba số nguyên A, B, K.
cpp-067Bước 2Nâng cao
Tối ưu hóa quy hoạch động Knuth (Knuth's Optimization)
opt(i, j-1) ≤ opt(i, j) ≤ opt(i+1, j)
cpp-182Bước 3Nâng cao
Digit DP: Đếm số đối xứng (Palindrome) trong đoạn [A, B]
Một số nguyên dương được gọi là số đối xứng (palindromic number) nếu nó đọc xuôi và đọc ngược đều giống nhau (ví dụ: 7, 33, 121, 4884). Số không có chữ số 0 vô nghĩa ở đầu.
cpp-098Bước 4Nâng cao
Dãy ngoặc hợp lệ dài nhất: Ngăn xếp và Quy hoạch động O(N)
Cho một chuỗi S chỉ gồm các ký tự '(' và ')'. Hãy tìm độ dài của chuỗi con liên tiếp dài nhất là dãy ngoặc hợp lệ.
cpp-160Bước 5Nâng cao
Cắt Thanh Gỗ Chi Phí Nhỏ Nhất (Minimum Cost to Cut a Stick)
Bạn có một thanh gỗ có độ dài L, được đánh dấu các vị trí từ 0 đến L. Có M nhát cắt cần thực hiện tại các vị trí nguyên cuts[1], cuts[2], …, cuts[M].
cpp-097Bước 6Nâng cao
Hình chữ nhật toàn số 1 lớn nhất trong ma trận nhị phân
Cho một ma trận nhị phân gồm N hàng và M cột, mỗi ô chỉ chứa giá trị 0 hoặc 1. Hãy tìm diện tích của hình chữ nhật lớn nhất chỉ chứa toàn các số 1.
cpp-159Bước 7Nâng cao
Đập Bóng Bay Thu Được Điểm Lớn Nhất (Burst Balloons)
Bạn có N quả bóng bay được xếp thành một hàng ngang, quả thứ i có điểm số là Ai.
Chuyên sâu
Cấu trúc dữ liệu nâng cao và nhiều bước chứng minh.
cpp-066Bước 8Nâng cao
Tối ưu hóa quy hoạch động Chia để trị (Divide and Conquer DP)
Cho một dãy gồm N số nguyên dương A1, A2, …, AN. Bạn cần phân chia dãy này thành đúng K đoạn con liên tiếp không rỗng. Chi phí của một đoạn từ chỉ số l đến r (1-indexed) là…
cpp-109Bước 9Nâng cao
Kỹ thuật Slope Trick: Tối ưu hóa hàm chi phí lồi
Cho một dãy gồm N số nguyên A1, A2, …, AN. Bạn cần tạo ra một dãy số nguyên không giảm B1 ≤ B2 ≤ … ≤ BN sao cho tổng khoảng cách:
cpp-110Bước 10Nâng cao
Kỹ thuật WQS Binary Search (Ali's Trick / Lagrange Multiplier DP)
Cho một mảng gồm N số nguyên A1, A2, …, AN. Bạn cần chọn ra đúng K đoạn con liên tiếp đôi một không giao nhau sao cho tổng các phần tử của K đoạn con được chọn là lớn nhất c…
cpp-016Bước 11Nâng cao
Quy hoạch động tìm Dãy con tăng dài nhất và truy vết
Hệ thống tính điểm năng lực học tập của AI Empire Academy ghi nhận chuỗi N thành tích qua các bài kiểm tra: A1, A2, …, AN (1 ≤ N ≤ 105, -109 ≤ Ai ≤ 109).
cpp-035Bước 12Nâng cao
Quy hoạch động chữ số (Digit DP) đếm số không chứa số 13
Hệ thống cấp phát định danh máy chủ bảo mật của AI Empire Academy quy định: Một số nguyên dương được coi là hợp lệ nếu trong biểu diễn thập phân của nó không chứa xâu con liên tiếp…
cpp-108Bước 13Nâng cao
Quy hoạch động trên biên dạng nứt (Broken Profile DP / Domino Tiling)
Cho một bảng lưới chữ nhật kích thước N × M. Hãy tính số cách lát kín bảng này bằng các thanh domino kích thước 1 × 2 và 2 × 1 modulo 109 + 7.
cpp-068Bước 14Nâng cao
Quy hoạch động trên tập con: SOS DP (Sum Over Subsets)
Cho một mảng A gồm 2N số nguyên (0 ≤ mask < 2N). Hãy tính mảng F gồm 2N số nguyên, trong đó:
Tối ưu & chứng minh
Ràng buộc chặt về thời gian và bộ nhớ — mức thi đấu.
cpp-186Bước 15Nâng cao
Nhân ma trận: Đếm số đường đi độ dài đúng K trên đồ thị có hướng
Cho đồ thị có hướng gồm N đỉnh (đánh số từ 0 đến N-1) và M cạnh có hướng.
cpp-065Bước 16Nâng cao
Tối ưu hóa quy hoạch động Convex Hull Trick (CHT)
Có N tác vụ, tác vụ thứ i có hệ số Ai và chi phí Bi. Dãy A và B thỏa mãn A1 < A2 < … < AN và B1 > B2 > … > BN > 0.
cpp-180Bước 17Nâng cao
Held-Karp: Bài toán người bán hàng qua tập trạm kiểm soát
Cho đồ thị vô hướng gồm N đỉnh (đánh số 0 đến N-1) và M cạnh có trọng số dương.
cpp-183Bước 18Nâng cao
Profile DP: Lát gạch bảng M x N bằng Domino và Tromino
Cho một lưới ô vuông kích thước M × N gồm M hàng và N cột.
cpp-031Bước 19Nâng cao
Quy hoạch động Bitmask: Bài toán người du lịch TSP
Robot tự hành chịu trách nhiệm bảo trì phần cứng các cụm máy chủ phân tán của AI Empire Academy cần xuất phát từ phòng điều hành trung tâm (đánh số 0), đi qua thăm và kiểm tra tất…
cpp-187Bước 20Nâng cao
Thuật toán Aho-Corasick DP: Đếm xâu không chứa các mẫu cấm
Cho tập hợp gồm M xâu mẫu cấm P = {p1, p2, …, pM} chỉ gồm các chữ cái tiếng Anh in thường ('a' đến 'z').