Mở đầu

Xin chào các bạn mình vẫn tiếp tục hoàn thành hành trình nắm vững cách giải các bài DP, nếu các bạn đã xem PHẦN 1 hoặc có kiến thức nền tảng về quy hoạch động thì hãy đọc tiếp. Còn nếu các bạn là người mới thì hãy back lại phần 1 đọc thật kĩ để nắm được foundation của DP trước khi đến phần 2 này. Bởi vì phần 2 là sự nâng cấp và độ khó sẽ được tăng lên rất nhiều.

Ở phần 1, tôi đã nói về DP với dạng Prefix DP tức là state hiện tại của bạn phụ thuộc vào trạng thái trước đó. Quay về ví dụ Coins Change, để tính số đồng xun nhỏ nhất cho mệnh giá amount thì với mọi đồng xu i bạn sẽ chuyển từ bài toán cha về subproblems với amount - i, tức là bạn đang tính toán trên một đường thẳng dựa vào những gì tính toán trước đó. Trong bài viết này tôi sẽ giới thiệu về Interval Dynamic Programming dịch trong tiếng Việt là Quy hoạch động trên khoảng.

Interval Dynamic Programming

Interval Dynamic Programming là một kỹ thuật lập trình động (DP) dùng để giải quyết các bài toán tối ưu hóa trên một khoảng (interval) của dữ liệu, thường là mảng, chuỗi hoặc dãy số. Thay vì xử lý tuyến tính từ đầu đến cuối (như DP 1D), Interval DP tập trung vào việc chia khoảng lớn thành các khoảng con, tính toán giá trị tối ưu cho từng khoảng con, rồi kết hợp chúng để tìm giải pháp cho khoảng lớn.

Tôi sẽ lấy ví dụ như này hãy tưởng tượng bạn đang chơi trò xếp hình. Mục tiêu là hoàn thiện mô hình hoàn chỉnh, nhưng bạn không "xây" một lèo từ đầu đến cuối – vì như vậy sẽ tốn sức, chậm chạp, và dễ hỏng. Thay vào đó, bạn chia mô hình thành các bộ phận nhỏ: đầu, tay, thân, chân... Mỗi bộ phận là một "subproblem" (vấn đề con) mà bạn phải lắp sao cho tốn ít sức nhất nhưng nhanh nhất (tối ưu hóa thời gian và công sức). Và sau khi tìm được cách lắp các bộ phận rời rạc tối ưu nhất bạn lắp chúng thành một mô hình hoàn chỉnh cũng được tối ưu từ các bộ phận nhỏ.

Bây giờ tôi sẽ đi đến một ví dụ để giúp các bạn hình dung về Interval DP nhé

Minimum Cost to Cut a Stick

Mình sẽ lấy bài leetcode làm ví dụ vì nó là đặc trưng cho dạng interval DP này. Trước khi bước vào giải bài toán, mình sẽ nhắc lại các bạn 3 bước giải DP:

• Bước 1: Mô tả cấu trúc của giải pháp tối ưu (Xác định cách subproblems kết hợp để tạo giải pháp toàn cục).
• Bước 2: Định nghĩa đệ quy giá trị giải pháp tối ưu (Xây dựng recurrence relation).
• Bước 3: Tính toán giá trị giải pháp tối ưu theo bottom-up/ top-down approach.

Bài toán

Hãy tưởng tượng bạn có một thanh gỗ dài n đơn vị (ví dụ n=6, thanh từ 0 đến 6). Trên thanh có các điểm đánh dấu mà bạn phải cắt hết (danh sách cuts, ví dụ cuts =[1,3] ). Mỗi lần cắt, chi phí bằng độ dài thanh đang cắt (cắt thanh dài 5 tốn 5). Sau khi cắt, thanh bị chia thành 2 mảnh nhỏ hơn, và bạn tiếp tục cắt các mảnh đó cho đến khi hết điểm cắt.

Câu hỏi đặt ra là: Thứ tự cắt nào sẽ cho tổng chi phí nhỏ nhất?

Ví dụ đơn giản: Thanh dài 6, cuts = [1,3].

• Nếu cắt ở 3 trước: Cắt thanh 6 thành 2 thanh 3 và 3 (chi phí 6). Rồi cắt mảnh 3 (từ 0-3) ở 1 thành 1 và 2 (chi phí 3). Tổng chi phí = 9.

• Nếu cắt ở 1 trước: Cắt thanh 6 thành thanh 1 và 5 (chi phí 6). Rồi cắt mảnh 5 (từ 1-6) ở 3 (lúc này 3 trở thành vị trí 2 trong mảnh 5) thành 2 thanh 2 và 3 (chi phí 5). Tổng chi phí = 11 (Chưa tối ưu). Đáp án tối ưu: 9 (cách 1).

Trước khi đi vào giải pháp, hãy hiểu tại sao đây lại là một bài toán Interval DP:

• Interval DP có đặc trưng chính là chia một khoảng lớn thành các khoảng con nhỏ hơn, sau đó kết hợp kết quả của các khoảng con để có được kết quả cho khoảng lớn.

Bước 1 - Mô tả cấu trúc của giải pháp tối ưu

Khác với bài toán Coins Change ở phần 1, sau khi chúng ta chọn được một đồng xu, chúng ta sẽ tính toán đệ quy dựa trên kết quả subproblem T(amount-i).

• T(coins, amount) = min(1 + T(coins, amount - i))

Giả sử tôi nằm mơ được báo mộng cắt ở vết thứ 3 trong thanh gỗ từ 0 - 6 là tối ưu nhất, Sau khi cắt tại vị trí thứ 3, thì thanh gỗ bị chia thành 2 khúc (0,3) và (4, 6), chúng ta sẽ tiếp tục tìm vết cắt tối ưu nhất trên 2 đoạn khúc gỗ mới này. Tức là sau khi chúng ta có 2 khúc gỗ coi như mới:

• Trên khúc gỗ (0-3), chúng ta sẽ tiếp tục đi tìm vết cắt tối ưu nhất.
• Trên khúc gỗ (4-6), chúng ta sẽ tiếp tục đi tìm vết cắt tối ưu nhất.

-> T(0,6) = 6-0 + T(0, 3) + T(4-6)

Chúng ta dừng khi cắt hết mọi ví trí trong tập vết cắt cuts. Tới đây bạn có thể thấy sự khác biết rằng tại mỗi vết cắt tôi sẽ tạo 2 subproblems mới và đệ quy giải tiếp tục trên 2 tập đó. Vậy tôi sẽ có solution cho bài toán này là với mọi khoảng i -> j ( thanh gỗ từ i đến j), tôi chọn 1 vết cắt k trong cuts , tôi sẽ được 2 khoảng con [i, k] và [k, j], rồi tính tổng chi phí.

• T(i, j) = length(i-j) + T(i, k) + T(k,j)

Bước 2 - Định nghĩa đệ quy giá trị giải pháp tối ưu (Xây dựng recurrence relation).

Từ cấu trúc ở Bước 1, tôi có thể định nghĩa recurrence relation cho bài toán như sau:

• Giả sử T(i, j) là chi phí cắt tối thiểu để cắt hết các vết cắt trong khoảng từ vị trí i đến j (thanh gỗ dài j - i).
• Base case: Nếu không có vết cắt nào trong khoảng [i, j] (tức là khoảng rỗng hoặc không cần cắt), thì T(i,j) = 0. Hoặc

Recurrence Relation: Để cắt khoảng [i,j], chúng ta phải chọn một vết cắt k nằm giữa i vàj (và k phải thuộc tập cuts). Chi phí sẽ bao gồm:

• Chi phí cắt tại k: bằng độ dài thanh hiện tại j-i
• Chi phí cắt khoảng con [i,k]: T(i,k)
• Chi phí cắt khoảng con [k,j]: T(k,j)

Chúng ta lấy giá trị tối thiểu qua tất cả các k có thể:

• T(i,j) = min{(j-i) + T(i,k) + T(k,j)} với mọi k thuộc cuts và i < k < j

Lưu ý: Tập cuts cần được sắp xếp trước để dễ dàng xác định các k nằm trong [i, j]. Recurrence này thể hiện rõ đặc trưng của Interval DP: chia khoảng lớn thành các khoảng con và kết hợp chúng.

Bước 3 - Tính toán giá trị giải pháp tối ưu theo bottom-up/ top-down approach.

Bởi vì DP sẽ giúp chúng ta tránh được tính toán lại các tập giá trị đã được tính toán bằng cách lưu trữ các kết quả trong một bảng hai chiều. Tuy nhiên, điểm mấu chốt ở đây là việc chọn không gian trạng thái phù hợp, thay vì định nghĩa dp[i][j] trên space của thanh gỗ (tạo ra bảng kích thước n×n với nhiều ô không sử dụng), chúng ta sử dụng một cách tiếp cận thông minh hơn là dp[i][j] đại diện cho chi phí tối thiểu để thực hiện tất cả các vết cắt nằm giữa hai điểm biên cuts[i] và cuts[j] trên thanh gỗ. Ở đây cần phân biệt rõ:

• i, j: chỉ số trong mảng cuts
• cuts[i], cuts[j]: vị trí thực tế trên thanh gỗ.
• Đoạn gỗ cần xử lý: từ vị trí cuts[i] đến cuts[j], có độ dài = cuts[j] - cuts[i]

Các vết cắt cần thực hiện: tất cả các điểm cắt nằm giữa cuts[i] và cuts[j] (không bao gồm hai điểm biên)

// Hàm chính để tính chi phí cắt tối thiểu
function minCostToCutStick(n, cuts): //Bước 1: Chuẩn bị dữ liệu //Thêm điểm đầu (0) và điểm cuối (n) vào danh sách cuts //Điều này giúp xử lý các trường hợp biên một cách thống nhất cuts = [0] + sorted(cuts) + [n] // Lấy số lượng điểm cuts sau khi thêm (bao gồm 0 và n) m = length(cuts) // Khởi tạo bảng dp 2D kích thước m x m, tất cả giá trị ban đầu là 0 // dp[i][j] sẽ lưu chi phí tối thiểu để cắt khoảng từ cuts[i] đến cuts[j] // dp[i][i] = 0 (khoảng rỗng, không cần cắt) // dp[i][i+1] = 0 (không có cuts giữa hai điểm liền kề) dp = tạo mảng 2D kích thước m x m, giá trị mặc định 0 // Bước 2: Lặp qua các độ dài khoảng (từ nhỏ đến lớn) - bottom-up // Bắt đầu từ độ dài 2 vì độ dài 1 không cần cắt (base case) for length from 2 to m-1: // Với mỗi độ dài, lặp qua các điểm bắt đầu i for i from 0 to m - length - 1: // Tính điểm kết thúc j = i + length j = i + length dp[i][j] = INFINITY // Bước 3: Lặp qua các vị trí cắt k có thể trong khoảng (i, j) // k phải nằm giữa i+1 và j-1, vì không cắt ở đầu hoặc cuối for k from i+1 to j-1: // Tính chi phí cắt tại k: độ dài thanh hiện tại (cuts[j] - cuts[i]) // Cộng với chi phí của hai khoảng con: dp[i][k] + dp[k][j] cost = (cuts[j] - cuts[i]) + dp[i][k] + dp[k][j] // Cập nhật dp[i][j] với giá trị nhỏ nhất // Lý do: Chọn vết cắt k cho chi phí tối ưu nhất dp[i][j] = min(dp[i][j], cost) // Kết quả cuối cùng là dp[0][m-1], tức chi phí cho toàn bộ thanh từ 0 đến n return dp[0][m-1] // Ví dụ sử dụng: minCostToCutStick(6, [1, 3]) nên trả về 9

Bước 1: Sắp xếp danh sách cuts và thêm giới hạn 0 và n để dễ xử lý khoảng

Chúng ta có thanh gỗ từ 0 đến n với các điểm cắt cuts. State dp[i][j] đại diện cho chi phí tối thiểu để cắt hết các điểm trong khoảng [cuts[i], cuts[j]].

Tại sao chúng ta phải thêm 0 và n vào danh sách cuts? Đây là một kỹ thuật rất quan trọng:

• Thêm 0 vào đầu: Đây là điểm bắt đầu của thanh gỗ, giúp chúng ta xử lý các trường hợp cắt từ đầu thanh
• Thêm n vào cuối: Đây là điểm kết thúc của thanh gỗ, giúp chúng ta xử lý các trường hợp cắt đến cuối thanh
• Với việc thêm này, state dp[i][j] sẽ đại diện cho chi phí cắt khoảng từ cuts[i] đến cuts[j], và chúng ta có thể xử lý tất cả các trường hợp biên một cách dễ dàng, và vì hai điểm 0 và n là điểm biên nên nó không thể cắt được.

Việc sort (sắp xếp) lại mảng cuts là cực kỳ quan trọng. Nó giúp chúng ta tính toán bottom-up từ việc cắt các vị trí nhỏ hơn lên đến các vết cắt vị trí lớn hơn.

• Đảm bảo rằng khi chúng ta tính toán dp[i][j], tất cả các dp[i][k] và dp[k][j] (với i < k < j) đã được tính toán trước đó
• Nếu các bạn nhìn vào Bước 2 đệ quy thì chúng ta luôn tính toán các vết cắt ở vị trí lớn hơn bằng cách đệ quy về các vết các nhỏ hơn ở trong thanh gỗ vừa bị cắt.

 cuts = [0] + sorted(cuts) + [n] // Lấy số lượng điểm cuts sau khi thêm (bao gồm 0 và n) m = length(cuts) // Khởi tạo bảng dp 2D kích thước m x m, tất cả giá trị ban đầu là 0 // dp[i][j] sẽ lưu chi phí tối thiểu để cắt khoảng từ cuts[i] đến cuts[j] dp = tạo mảng 2D kích thước m x m, giá trị mặc định 0

Bước 2: Lặp qua các độ dài khoảng (từ nhỏ đến lớn) - bottom-up

 // Bắt đầu từ độ dài 2 vì độ dài 1 không cần cắt (base case) for length from 2 to m-1: // Với mỗi độ dài, lặp qua các điểm bắt đầu i for i from 0 to m - length - 1: // Tính điểm kết thúc j = i + length j = i + length

LƯU Ý QUAN TRỌNG: length ở đây là số lượng phần tử (khoảng cách chỉ số) trong mảng cuts, không phải độ dài vật lý của thanh gỗ. Cụ thể, length = j - i đại diện cho khoảng cách giữa hai chỉ số i và j trong mảng cuts.

WHY lặp theo độ dài (length) từ nhỏ đến lớn?

Đây là điểm cốt lõi của bottom-up approach trong Interval DP. Hãy suy nghĩ về dependencies (sự phụ thuộc). Khi chúng ta tính dp[i][j], chúng ta cần sử dụng các giá trị dp[i][k] và dp[k][j] với i < k < j. Điều này có nghĩa là:

• dp[i][k] tương ứng với khoảng có độ dài k - i (nhỏ hơn j - i)
• dp[k][j] tương ứng với khoảng có độ dài j - k (nhỏ hơn j - i) Vì vậy, các subproblem nhỏ phải được tính trước các subproblem lớn. Điều này đảm bảo rằng khi chúng ta cần một giá trị, nó đã được tính toán và có sẵn.

Với mỗi độ dài cố định, lặp qua các vị trí bắt đầu (i) có thể. Giới hạn đến m - length - 1 để j không vượt quá m-1 (tránh lỗi index out of bound). Tức là nó liệt kê tất cả khoảng bắt đầu từ i, với độ dài length. Mỗi i đại diện một "điểm khởi đầu" trong mảng cuts.

• Điểm khởi đầu vị trí i ở thanh gỗ cho đến vị trí j = i + length: Có nghĩa là Tính vị trí kết thúc j dựa trên i và length. j luôn lớn hơn i, tạo thành khoảng [i,j]. Tại sao? Nó "cắt" mảng cuts thành interval từ i đến j, để tính dp[i][j] (chi phí cho mảnh gỗ từ cuts[i] đến cuts[j]).
• Ví dụ: i=0, length=2 → j=2 → interval (vị trí cuts: 0,1,3 – mảnh gỗ từ 0 đến 3, có điểm cắt tại 1).

Hãy để não bạn thong thả hiểu chỗ này với các khúc gỗ có vị trí 2 điểm cắt gần nhất với length = 2 rồi sau đó tôi sẽ cho bạn thấy khi length = 3 chúng ta sẽ đệ quy/ tính toán dựa trên **length = 2 **như thế nào.

Bước 3: Lặp qua các vị trí cắt k có thể trong khoảng (i, j)

Sau khi xác định khoảng [i, j] ở Bước 2, ta thử mọi vị trí cắt k bên trong khoảng đó, tính chi phí nếu cắt tại k, và chọn chi phí nhỏ nhất để lưu vào dp[i][j]. Điều này thể hiện ý tưởng DP: chia vấn đề lớn thành nhỏ (cắt thành [i,k] và [k,j]), cộng chi phí và lấy min.

• Chi phí cắt : cost = (cuts[j] - cuts[i]) + dp[i][k] + dp[k][j] : Chúng ta đang tính chi phí cắt tại k với độ dài thanh hiện tại (cuts[j] - cuts[i]) và đây cũng là chi phí của lần cắt này, vì cắt thanh dài cuts[j] - cuts[i] tốn đúng bằng độ dài đó. Rồi cuối cùng cộng với chi phí của hai khoảng con: dp[i][k](phần trái) + dp[k][j] (phần phải)
• Sau đó chúng ta sẽ cập nhật dp[i][j] với giá trị nhỏ nhất. Tôi phải chọn vết cắt k cho chi phí tối ưu nhất, so sánh với các k khác và giữ min: dp[i][j] = min(dp[i][j], cost)

 // Bước 3: Lặp qua các vị trí cắt k có thể trong khoảng (i, j) // k phải nằm giữa i+1 và j-1, vì không cắt ở đầu hoặc cuối for k from i+1 to j-1: // Tính chi phí cắt tại k: độ dài thanh hiện tại (cuts[j] - cuts[i]) // Cộng với chi phí của hai khoảng con: dp[i][k] + dp[k][j] cost = (cuts[j] - cuts[i]) + dp[i][k] + dp[k][j] // Cập nhật dp[i][j] với giá trị nhỏ nhất // Lý do: Chọn vết cắt k cho chi phí tối ưu nhất dp[i][j] = min(dp[i][j], cost)

Ví dụ ở trên chúng ta đã tính ra optimal result (kết quả tối ưu) cho length interval mỗi khúc gỗ là 2. Bây giờ chúng ta sẽ tăng length lên = 3, và tiếp tục loop để tính các khoảng length bằng 3 với các vị trí cuts[i] bắt đầu.

• Bắt đầu tại vị trí cuts[0] - > cuts[3], nó sẽ có 2 vị trí cắt k tại cuts[1] và cuts[2]. Và sau khi cắt các homies thấy nó chia ra 2 thanh gỗ length = 1 (không thể cắt nữa nên = 0) và length = 2 (kết quả đã được tính toán khi loop length = 2 chạy trước đó), trong trường hợp này, chúng ta thấy vết cắt cuts[2] hoặc cuts[1] đều cho kết quả tối ưu nên chúng ta chọn 1 trong 2

• Bắt đầu tại vị trí cuts[1] - > cuts[4], nó sẽ có 2 vị trí cắt k tại cuts[2] và cuts[3], trong trường hợp này, chúng ta thấy vết cắt cuts[3] cho kết quả tối ưu nên chúng ta chọn cuts[3].

• Bắt đầu tại vị trí cuts[2] - > cuts[5], nó sẽ có 2 vị trí cắt k tại cuts[3] và cuts[4], trong trường hợp này, chúng ta thấy vết cắt cuts[3] hay cuts[4] đều cho kết quả tối ưu nên chúng ta chọn cuts[3].

Và tiếp nữa thì các bạn hãy tiếp tục tự mình suy nghĩ và vẽ ra từng bước để thấy rằng các khoảng với độ dài lơn hơn nó sẽ được tính toán dựa trên các khoảng nhỏ hơn như thế nào nhé

Sau tất cả vòng lặp: Kết quả cuối cùng là dp[0][m-1], tức chi phí cho toàn bộ thanh từ 0 đến n. Tức là [0, m-1] tương ứng khoảng từ cuts[0]=0 đến cuts[m-1]=n.

Tại sao Interval DP hiệu quả

Interval Dynamic Programming đặc biệt phù hợp với bài toán Minimum Cost to Cut a Stick vì những lý do sau:

• Cấu trúc Subproblems tự nhiên: Mỗi lần cắt tạo ra hai khoảng con hoàn toàn độc lập. Việc cắt trên khoảng này không ảnh hưởng đến việc cắt trên khoảng kia.
• Optimal Substructure (Cấu trúc Con Tối ưu): Giải pháp tối ưu cho khoảng lớn được xây dựng từ giải pháp tối ưu của các khoảng con. Nếu chúng ta biết cách cắt tối ưu cho hai khoảng con, chúng ta có thể xây dựng giải pháp tối ưu cho khoảng lớn.
• Overlapping Subproblems: Nhiều khoảng con được tính toán lại trong các trường hợp khác nhau. Ví dụ, khoảng [i, k] có thể xuất hiện trong nhiều cách phân chia khác nhau. DP giúp chúng ta tránh tính toán lại bằng cách lưu trữ kết quả.
• Tính Độc lập của Subproblems: Sau khi cắt tại một vị trí, hai khoảng con trở nên hoàn toàn độc lập. Điều này cho phép chúng ta áp dụng nguyên lý "chia để trị" một cách hiệu quả.

Phân tích Độ phức tạp

• Độ phức tạp Thời gian: O(n³)

  • Có O(n²) cặp (i,j) cần tính toán
  • Với mỗi cặp (i,j), chúng ta thử O(k) vị trí cắt k
  • Tổng cộng: O(n²) × O(k) = O(n²xk)

• Độ phức tạp Không gian: O(n²)

  • Bảng DP có kích thước n × n, Mỗi ô lưu trữ một giá trị chi phí

So sánh với Các Approach Khác

1. Brute Force (Vét cạn):

• Thử tất cả các permutation của thứ tự cắt
• Độ phức tạp: O(n! × n) - không khả thi với n lớn
• Không tận dụng được tính chất overlapping subproblems

2. Greedy Approach:

• Luôn chọn vị trí cắt "tốt nhất" ở mỗi bước
• Không đảm bảo kết quả tối ưu toàn cục
• Phản ví dụ: Có thể có trường hợp lựa chọn tại chỗ không tối ưu nhưng dẫn đến kết quả tổng thể tốt hơn

3. Top-down DP (Memoization):

• Cũng có độ phức tạp O(n³) như bottom-up
• Nhưng có thể có overhead từ recursive calls
• Dễ viết hơn nhưng có thể gặp stack overflow với input lớn

4. Bottom-up DP (Interval DP - Approach hiện tại):

• Tối ưu về mặt thời gian và không gian
• Không có overhead từ recursion
• Dễ kiểm soát thứ tự tính toán

Cách nhận biết Interval DP

Interval DP thường được sử dụng khi bài toán có những đặc điểm sau:

• Cấu trúc Khoảng: Bài toán có thể được biểu diễn dưới dạng các khoảng [i, j].
• Điểm Chia: Có thể chọn một điểm k để chia khoảng [i, j] thành [i, k] và [k, j].
• Tính Độc lập: Hai khoảng con sau khi chia là độc lập với nhau.
• Optimal Substructure: Giải pháp tối ưu cho khoảng lớn được xây dựng từ giải pháp tối ưu của các khoảng con.

Tổng kết

Các bài toán kinh điển khác sử dụng Interval DP để các bạn có thể luyện thêm