Số chính phương trong C++

Giả sử chúng ta có một số nguyên dương n, 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à 13, đầu ra là 2, vì các số là 13 = 9 + 4.

Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:

Tạo một bảng quy hoạch động, độ dài n + 1, và điền bằng vô cực
dp[0] := 0
for i := 1, khi i*i <= n
- x = i * i
- for j := x đến n
  - dp[j] := min của dp[j] và 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 numSquares(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];
    }
};
main(){
    Solution ob;
    cout << (ob.numSquares(147));
}

Số chính phương trong C++

Ví dụ

Đầu vào

Đầu ra