Nguồn: Free Contest

Gọi ~dp[i][j]~ là tổng điểm số lớn nhất có thể đạt được ở ~i~ lượt ném đầu tiên và quả bong bóng được chọn trong lượt ném cuối cùng là ~j~. Ta có công thức quy hoạch động sau:

~dp[i][j]~ = ~A_j \times i + max(dp[i - 1][k])~ \(∀j - M \le k < j\)

Việc tính nhanh công thức quy hoạch động trên tương đương bài toán tìm giá trị lớn nhất trong đoạn tịnh tiến.

Độ phức tạp: ~O(N.K)~