[leetcode 279] Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.

 

주어진 n을 제곱수의 합으로 표현할 때 가장 적은 숫자의 제곱수

 

- 풀이:

dp[n]은 return값이다.

bottom-up으로 update해나간다.

dp[i] = i로 초기화하고 i보다 작거나 같은 제곱수를 빼서 값을 update한다.

제곱수는 dp[j*j] = 1 ㅇㅣ니까 +1만 해주면 된다.

using namespace std;
class Solution {
public:
    int numSquares(int n) {
        
        vector<int> dp(n+1,0);
        dp[0] = 0;
        for(int i=1; i <=n; i++){
            dp[i] = i;
            for(int j=1; j*j<=i; j++){
                dp[i] = min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
        
    }
};