Module 1 — Bảng Interval DP điền theo đường chéo
Bảng dp[i][j] chỉ dùng nửa trên-phải (i ≤ j). Đường chéo chính là base case (độ dài 1).
Mỗi bước điền một đường chéo ứng với một độ dài khoảng tăng dần. Ô xanh nhạt = khoảng con
mà dp[i][j] đang đọc (phụ thuộc). Đây là demo với Matrix Chain (chi phí nhân scalar).
Quan sát: ô kết quả dp[0][n-1] ở góc trên-phải được điền cuối cùng — vì nó cần mọi khoảng con ngắn hơn.
Module 2 — Matrix Chain: thử mọi cách đặt ngoặc
Nhân ma trận có tính kết hợp (AB)C = A(BC) nhưng số phép nhân scalar khác nhau.
Module này liệt kê mọi cách đặt ngoặc và chi phí, đánh dấu tối ưu
(xanh) và tệ nhất (đỏ).
Số cách đặt ngoặc của n ma trận = số Catalan C(n-1). Interval DP né việc liệt kê tất cả (vốn cấp số mũ) bằng cách nhớ dp[i][j].
Module 3 — Burst Balloons: bóng "nổ cuối cùng"
Mẹo: thay vì hỏi "nổ bóng nào TRƯỚC", ta hỏi "trong khoảng (i, j), bóng nào nổ CUỐI CÙNG".
Khi đó hai hàng xóm của nó là hai biên i, j (cố định) → điểm = a[i]·a[k]·a[j],
hai nửa độc lập. Có thêm biên ảo 1 ở hai đầu.
Khoảng (i, j) là khoảng MỞ — không nổ i, j. Transition dùng dp[i][k] + dp[k][j] (chú ý dp[k][j], không phải dp[k+1][j]).