จำนวนกำลังสองสมบูรณ์ใน C++

สมมติว่าเรามีจำนวนเต็มบวก n ให้หาจำนวนน้อยที่สุดของจำนวนกำลังสองสมบูรณ์ที่ผลรวมของพวกเขาเท่ากับ n ดังนั้นถ้าตัวเลขคือ 13 ผลลัพธ์คือ 2 เพราะตัวเลขคือ 13 = 9 + 4

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

สร้างตารางสำหรับ Dynamic Programming ความยาว n + 1 และเติมด้วย infinity
dp[0] := 0
for i := 1, เมื่อ i*i <= n
- x = i * i
- for j := x ถึง n
  - dp[j] := ค่าต่ำสุดของ dp[j] และ 1 + dp[j - x]
return dp[n]

ลองดูการนำไปใช้ต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่างโค้ด

#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));
}

จำนวนกำลังสองสมบูรณ์ใน C++

ตัวอย่างโค้ด

อินพุต

เอาต์พุต