Gọi ~dp[i][j]~ là số điểm bị trừ ít nhất khi đã bắn hết ~i~ tàu đầu tiên và đã dùng ~j~ tầm bắn. Xây dựng công thức quy hoạch động ta có:

$$dp[i][j] = min^{i}_{k = 1} ( dp[k - 1][j - 1] + max(a_k, a_{k + 1}, \ldots, a_i) * (i - k + 1) - (a_k + a_{k + 1} + \ldots + a_i))$$

Khởi tạo mảng ~dp~ ban đầu là ~\infty~, còn ~dp[0][0] = 0~.

Đán án của bài toán là ~dp[n][k + 1]~.

Tổng độ phức tạp cho bài toán là ~O(N^2 * K)~.