Chương trình đếm số chính phương cộng lại thành một số trong C++

Giả sử có một số dương n, ta phải tìm số lượng ít nhất các số chính phương mà tổng của chúng bằng n. Vì vậy nếu số là 10, đầu ra là 2, vì 10 = 9 + 1.

Để giải quyết, ta làm theo các bước sau:

• tạo bảng quy hoạch động độ dài n+1, điền vô cực
• dp[0] := 0
• với i := 1, khi i*i <= n
  • x = i * i
  • với j := x đến n
    • dp[j] := min(dp[j], 1 + dp[j - x])
• trả về dp[n]

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

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

#define INF 1e9

class Solution {
public:
    int solve(int n) {
        vector<int> dp(n+1, INF);
        dp[0] = 0;
        for(int i = 1; i*i <= n; i++) {
            int x = i*i;
            for(int j = x; j <= n; j++) {
                dp[j] = min(dp[j], 1 + dp[j-x]);
            }
        }
        return dp[n];
    }
};

int main() {
    Solution ob;
    cout << ob.solve(10);
    return 0;
}

Đầu vào

10

Đầu ra

2