สมมติว่าเรามีจำนวนเต็มบวก n จงหาจำนวนที่น้อยที่สุดของจำนวนเต็มกำลังสองสมบูรณ์ที่ผลรวมเป็น n ดังนั้นหากตัวเลขคือ 13 ผลลัพธ์ก็คือ 2 เนื่องจากตัวเลขคือ 13 =9 + 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างตารางหนึ่งตารางสำหรับโปรแกรมไดนามิก ความยาว 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 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));
} อินพุต
147
ผลลัพธ์
3
