Giả sử chúng ta có một số dương n, chúng ta phải tìm số ít nhất trong các số vuông hoàn hảo có tổng bằng n. Vì vậy, nếu số là 10, thì đầu ra là 2, vì các số là 10 =9 + 1.
Để 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 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);
} Đầu vào
10
Đầu ra
2