Hình vuông hoàn hảo trong C ++

Giả sử chúng ta có một số nguyên dương n, hãy tìm số ít nhất trong các số vuông hoàn hảo có tổng là n. Vì vậy, nếu số là 13, thì đầu ra là 2, vì các số là 13 =9 + 4

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một bảng để lập trình động, có độ dài n + 1 và điền vào nó bằng vô cực
• dp [0]:=0
• đối với i:=1, khi i * i <=n
  • x =i * i
  • for j:=x to n
    • dp [j]:=tối thiểu là dp [j] và 1 + dp [j - x]
• trả về dp [n]

Hãy cùng chúng tôi xem cách 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));
}

Đầu vào

147

Đầu ra

3