양의 정수 n이 있다고 가정하고 합이 n인 완전제곱수의 최소 개수를 찾습니다. 따라서 숫자가 13이면 숫자가 13 =9 + 4이므로 출력은 2입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 길이가 n + 1인 동적 프로그래밍을 위한 하나의 테이블을 만들고 무한대로 채웁니다.
- dp[0] :=0
- for 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