Số Lượng Số Chính Phương Nhỏ Nhất Tổng Bằng n

Giới thiệu

Mọi số tự nhiên đều có thể biểu diễn dưới dạng tổng của các số chính phương. Bài toán: tìm số lượng ít nhất các số chính phương cần để tổng bằng n.

Đầu vào và Đầu ra

Đầu vào: n = 63
Đầu ra: 4 (63 = 7² + 3² + 2² + 1²).

Thuật toán Quy hoạch động

Mảng sqList[i] lưu số lượng ít nhất để biểu diễn i. Khởi tạo sqList[0..3] = 0,1,2,3. Với i từ 4 đến n, thử mọi x sao cho x² ≤ i, cập nhật sqList[i] = min(sqList[i], 1 + sqList[i - x²]).

minSquareTerms(value)
Begin
    định nghĩa sqList[0..value]
    sqList[0]=0, sqList[1]=1, sqList[2]=2, sqList[3]=3
    for i := 4 to value do
        sqList[i] := i
        for x := 1 to i do
            temp := x*x
            if temp > i then break
            else sqList[i] := min(sqList[i], 1 + sqList[i - temp])
        done
    done
    return sqList[value]
End

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;

int min(int x, int y) { return (x < y) ? x : y; }

int minSquareTerms(int n) {
    int *squareList = new int[n+1];
    squareList[0] = 0; squareList[1] = 1; squareList[2] = 2; squareList[3] = 3;
    for (int i = 4; i <= n; i++) {
        squareList[i] = i;
        for (int x = 1; x <= i; x++) {
            int temp = x*x;
            if (temp > i) break;
            else squareList[i] = min(squareList[i], 1 + squareList[i - temp]);
        }
    }
    return squareList[n];
}

int main() {
    int n;
    cout << "Nhập một số: "; cin >> n;
    cout << "Số hạng chính phương tối thiểu: " << minSquareTerms(n);
    return 0;
}

Kết quả

Nhập một số: 63
Số hạng chính phương tối thiểu: 4