Quy hoạch động tối ưu

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 6)

Quy hoạch động tối ưu

Aliens Trick (WQS Binary Search)

Thời gian (Time) O(N log C)
Không gian (Space) O(N)

Mô tả nguyên lý

Kỹ thuật tìm kiếm nhị phân trên chi phí phạt (penalty) để giải các bài toán ràng buộc số lượng phần tử trong DP.

Cài đặt mẫu (Implementation)

// Chuyển đổi bài toán ràng buộc chính xác K phần tử thành bài toán tối ưu tự do với hệ số phạt.
Quy hoạch động tối ưu

Convex Hull Trick (CHT)

Thời gian (Time) O(1) amortized
Không gian (Space) O(N)

Mô tả nguyên lý

Tối ưu hóa các biểu thức quy hoạch động dạng tuyến tính $dp[i] = \min_j (m_j \cdot x_i + c_j)$.

Cài đặt mẫu (Implementation)

// Duy trì tập hợp các đường thẳng tạo thành bao lồi để tìm giá trị tối ưu cực nhanh.
Quy hoạch động tối ưu

Divide and Conquer DP Optimization

Thời gian (Time) O(N log N)
Không gian (Space) O(N * K)

Mô tả nguyên lý

Tối ưu hóa độ phức tạp của các bài toán DP có dạng $dp[i][j] = \min_k (dp[i-1][k] + C[k][j])$.

Cài đặt mẫu (Implementation)

// Áp dụng chia để trị trên ma trận trạng thái để giảm một chiều tính toán từ $O(N^2)$ xuống $O(N \log N)$.
Quy hoạch động tối ưu

Knuth Optimization for DP

Thời gian (Time) O(N^2)
Không gian (Space) O(N^2)

Mô tả nguyên lý

Tối ưu hóa các bài toán quy hoạch động khoảng cách thỏa mãn tính chất tứ giác (Quadrangle Inequality).

Cài đặt mẫu (Implementation)

// Giới hạn khoảng tìm kiếm điểm tối ưu k dựa trên tính chất đơn điệu của điểm cắt.
Quy hoạch động tối ưu

Monotone Queue DP Optimization

Thời gian (Time) O(N)
Không gian (Space) O(N)

Mô tả nguyên lý

Tối ưu hóa các bài toán trượt cửa sổ trong quy hoạch động sử dụng hàng đợi đơn điệu.

Cài đặt mẫu (Implementation)

// Loại bỏ các phần tử kém tối ưu ra khỏi hàng đợi để luôn giữ phần tử tốt nhất ở đầu.
Quy hoạch động tối ưu

Slope Trick

Thời gian (Time) O(N log N)
Không gian (Space) O(N)

Mô tả nguyên lý

Duy trì các hàm lồi bằng cách lưu trữ các điểm uốn (slope changes) qua hàng đợi ưu tiên.

Cài đặt mẫu (Implementation)

// Giải quyết các bài toán tối ưu hóa chi phí tuyệt đối với hàm chi phí lồi.