Quy hoạch động là một trong các mô hình thuật toán. Cách tiếp cận này chia bài toán thành các bài toán con và lưu kết quả của các bài toán con trước để dùng sau, giúp giảm thời gian tính toán.
Có hai loại kỹ thuật Quy hoạch động:
- Bài toán con chồng chéo (Overlapping Subproblem)
- Cấu trúc con tối ưu (Optimal Substructure)
Trong phần này sẽ bao gồm:
- Bài toán Xếp hộp (Box Stacking)
- Thu thập điểm tối đa trong lưới bằng hai lần duyệt
- Tính tổng chữ số từ 1 đến n
- Đếm chuỗi nhị phân không có 1 liên tiếp
- Đếm số cách đạt điểm cho trước trong trò chơi
- Đếm cách xây dựng tòa nhà
- Đếm cách lên đến bậc n của cầu thang
- Khoảng cách chỉnh sửa (Edit Distance)
- Bài toán Rơi trứng (Egg Dropping Puzzle)
- Tìm số có tổng chữ số bằng giá trị cho trước
- Chi phí tối thiểu đến đích
- Thuật toán Floyd-Warshall
- Tạo dãy Fibonacci
- Số 'A' tối đa với 4 phím
- Bài toán tập độc lập lớn nhất
- Tổng dãy con liên tiếp lớn nhất (Kadane)
- Dãy con Bitonic dài nhất
- Dãy con chung dài nhất (LCS)
- Đường đi liên tiếp dài nhất từ ký tự cho trước
- Dãy con tăng dần dài nhất (LIS)
- Độ dài dãy con đối xứng dài nhất
- Dãy con đối xứng dài nhất (Substring)
- Nhân chuỗi ma trận (Matrix Chain Multiplication)
- Độ dài cặp chuỗi tối đa
- Lợi nhuận tối đa mua bán cổ phiếu hai lần
- Ma trận con vuông toàn 1 lớn nhất
- Dãy con tăng dần tổng lớn nhất
- Tổng lớn nhất hình chữ nhật trong ma trận
- Tìm đường đi chi phí nhỏ nhất từ ma trận
- Chi phí tối thiểu tam giác hóa đa giác
- Số token tối thiểu đến đích
- Bài toán Đổi tiền tối thiểu
- Số nhảy tối thiểu
- Tổng số chính phương nhỏ nhất để đạt giá trị
- Bài toán bàn phím di động
- Tổng lớn nhất bằng cách chia số thành 3 lần
- Chi phí BST tối ưu
- Bài toán Ghép đôi bạn bè
- Bài toán Khớp mẫu ký tự đại diện (Wildcard Pattern Matching)
- Phân hoạch chuỗi đối xứng (Palindrome Partitioning)
- Kiểm tra khả năng phân chia tập thành tổng bằng nhau
- Bài toán Cắt thanh (Rod Cutting)
- Dãy con chung ngắn nhất (Shortest Common Super-Sequence)
- Bài toán Tổng tập con (Subset Sum)
- Số không giảm trong giá trị N chữ số
- Số Ugly (Ugly Numbers)
- Bài toán phủ đỉnh (vertex covering)
- Bài toán Lập lịch công việc có trọng số
- Bài toán Ngắt dòng (Word Wrap)