Câu hỏi

Cho một số nguyên dương n, tìm số lượng số chính phương ít nhất có tổng là n.

Ví dụ: Với n là 9, thì đáp án là 1 (vì 9 là số chính phương), với n là 10 thì đáp án là 2 (9 + 1), với n là 11, đáp án là 3 (9 + 1 + 1), với n là 12 thì đáp án là 3 (4 + 4 + 4).

Phân tích

Giả sử như ta đã có đáp án cho tất cả các giá trị từ 1 đến n-1, đáp án cho n sẽ là min(1 + đáp án của (n-x)) với x là một số chính phương. Nói một cách khác, với mỗi số chính phương x nhỏ hơn hoặc bằng n, số lượng số chính phương cần để có tổng là n sẽ là số lượng số chính phương cần để tạo ra tổng là n-x thêm 1 (chính là x). Do đó, đáp án cho n sẽ chính là min của các cách tạo ra tổng n từ các số chính phương nhỏ hơn hoặc bằng n.

Như vậy, ta có thể giải bài toán này bằng cách điền vào bảng trả lời (đặt tên là ans) cho các giá trị từ 0 đến n. Kết quả cuối cùng sẽ là giá trị của ans[n].

Cách giải các bài toán mà đáp án cho giá trị cuối cùng có thể được tính từ đáp án của các giá trị trước, và ta có thể tính các giá trị này bằng cách từ từ điền vào bảng, được gọi là quy hoạch động (dynamic programming).

def solve(n):
    ans = [n] * (n + 1)
    ans[0] = 0
    ans[1] = 1
    for i in xrange(2, n + 1):
        x = 0
        while True:
            x += 1
            x2 = x * x
            if x2 > i:
                break
            ans[i] = min(ans[i], 1 + ans[i - x2])
    return ans[n]

assert(solve(9) == 1)
assert(solve(10) == 2)
assert(solve(11) == 3)
assert(solve(12) == 3)

Độ phức tạp thực thi của cách giải này là O(n * sqrt(n)), và tốn O(n) bộ nhớ.