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.

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.

cơ bản

Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.

trung bình

Kết hợp nhiều bước suy luận để vận dụng kiến thức.

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.

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.

•

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.

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.

Cơ bản 14 bài

Khởi động

Nhập xuất, biến, rẽ nhánh và các bước suy luận đơn giản.

cpp-287Bước 1Cơ bản

Tính số hạng thứ n của dãy Tribonacci

Dãy Tribonacci là bản mở rộng của dãy Fibonacci khi mỗi số hạng bằng tổng ba số hạng liền

cpp-277Bước 2Cơ bản

Đếm số cách leo cầu thang với bước 1 hoặc 2 bậc

Một cầu thang có n bậc. Mỗi lần bước, bạn chỉ được bước lên 1 bậc hoặc 2 bậc. Đây là

cpp-284Bước 3Cơ bản

Đếm số đường đi trong lưới chỉ đi sang phải và xuống dưới

Đây là bài quy hoạch động trên lưới đầu tiên: mỗi ô trong lưới nhận đóng góp từ ô phía trên

cpp-290Bước 4Cơ bản

In hàng thứ n của tam giác Pascal

Mỗi hàng của tam giác Pascal được sinh từ hàng ngay trên nó: hai ô kề nhau cộng lại thành ô

cpp-278Bước 5Cơ bản

Đếm số cách leo cầu thang với bước dài từ 1 tới k

Bản mở rộng của bài leo cầu thang kinh điển: thay vì chỉ hai cỡ bước 1 và 2, người ta

cpp-285Bước 6Cơ bản

Tổng đường đi nhỏ nhất trong lưới

Thay vì đếm đường đi, bài này hỏi đường đi nào tốn ít chi phí nhất. Mỗi ô có một chi phí, và

cpp-286Bước 7Cơ bản

Đếm xâu nhị phân không có hai ký tự 1 kề nhau

Nhiều bài quy hoạch động cần nhớ trạng thái của ký tự cuối cùng chứ không chỉ vị trí đang xét.

Làm quen

Vòng lặp, mảng một chiều, chuỗi và hàm ở mức cơ bản.

cpp-279Bước 8Cơ bản

Đổi tiền bằng ít đồng xu nhất

Bạn có một danh sách mệnh giá đồng xu và không hạn chế số lượng mỗi loại. Câu hỏi đặt ra là

cpp-280Bước 9Cơ bản

Đếm số cách đổi tiền không phân biệt thứ tự

Cùng một số tiền có thể được ghép từ các đồng xu theo nhiều cách, nhưng 1 + 2 và 2 + 1

cpp-281Bước 10Cơ bản

Ba lô 0/1 với sức chứa nhỏ

Ba lô 0/1 là bài quy hoạch động kinh điển thứ hai sau bài leo cầu thang. Mỗi món đồ chỉ có

cpp-282Bước 11Cơ bản

Độ dài dãy con chung dài nhất của hai xâu ngắn

Dãy con của một xâu là xâu nhận được bằng cách xoá bớt một số ký tự nhưng giữ nguyên thứ tự

cpp-283Bước 12Cơ bản

Tổng lớn nhất khi không lấy hai phần tử kề nhau

Cho một dãy số dương, ta muốn chọn ra một nhóm phần tử có tổng lớn nhất nhưng không được chọn

cpp-288Bước 13Cơ bản

Số chính phương ít nhất để biểu diễn n

Mọi số nguyên dương đều viết được thành tổng các số chính phương, nhưng số lượng số chính

cpp-289Bước 14Cơ bản

Khoảng cách chỉnh sửa giữa hai xâu ngắn

Khoảng cách chỉnh sửa (còn gọi là khoảng cách Levenshtein) là số phép biến đổi ít nhất để biến

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-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.

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(N²).

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 C₁, C₂, …, C_N. 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 A₁, A₂, …, A_N đượ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ự S₁, S₂, S₃.

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 A₁, A₂, …, A_N. Ma trận A_i có kích thước P_i-1 × P_i.

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 A₁, A₂, …, A_N.

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à C_i (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 ≤ 10⁴). 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à A_i.

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 A₁, A₂, …, A_N. 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 A₁, A₂, …, A_N. Bạn cần tạo ra một dãy số nguyên không giảm B₁ ≤ B₂ ≤ … ≤ B_N 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 A₁, A₂, …, A_N. 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: A₁, A₂, …, A_N (1 ≤ N ≤ 10⁵, -10⁹ ≤ A_i ≤ 10⁹).

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 10⁹ + 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 2^N số nguyên (0 ≤ mask < 2^N). Hãy tính mảng F gồm 2^N 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

Lộ trình thực hành đề xuất

DP 1 Chiều cơ bản

Dãy con tăng dài nhất (LIS)

Bài toán Cái ba lô (Knapsack)

Xâu con chung dài nhất (LCS)

DP Trạng thái (Bitmask DP)

Lỗi thường gặp & Cách phòng tránh

Danh sách bài tập thực hành (46 bài)

Cơ bản 14 bài

Khởi động

Làm quen

Trung bình 12 bài

Vận dụng

Kết hợp kỹ thuật

Nâng cao 20 bài

Thử thách

Chuyên sâu

Tối ưu & chứng minh

Chuyên đề liên quan thuộc môn C++

C++ Cơ bản

Mảng & Kỹ thuật mảng

Lý thuyết đồ thị C++

Xâu ký tự & Thuật toán xâu