Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

โปรแกรมนับจำนวนกำลังสองสมบูรณ์จะถูกรวมเป็นตัวเลขในภาษา C++


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

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

  • สร้างตารางหนึ่งตารางสำหรับโปรแกรมไดนามิก ความยาว n + 1 และเติมด้วยอินฟินิตี้
  • dp[0] :=0
  • สำหรับ i :=1 เมื่อ i*i <=n
    • x =ฉัน * ฉัน
    • สำหรับ j :=x ถึง n
      • dp[j] :=ขั้นต่ำของ dp[j] และ 1 + dp[j – x]
  • ส่งคืน dp[n]

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

ตัวอย่าง

#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];
   }
};
main(){
   Solution ob;
   cout << ob.solve(10);
}

อินพุต

10

ผลลัพธ์

2