Leetcode - 279. Perfect Squares

문제

어떤 수를 1, 4, 9, 16과 같은 완전제곱수(Perfect Square)의 합으로 나타낼수 있을때, 해당 수를 표현할 수 있는 최소한의 완전제곱수의 갯수는 몇개 인가?

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

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

해결 아이디어

f(n) = min(f(n - 1^2), ~ , f(n - i^2)) + 1 이라는 점화식 관계를 구할 수 있음. 단 i 는 i*i <= n 까지

해결

backtracking + memoization으로 해결

class Solution {
    int mem[10001];
public:
    int numSquares(int n) {
        int ret = INT_MAX;
        if (mem[n])
            return mem[n];
        if (n == 0)
            return 0;
        
        for (int i = 1; i*i <= n; i++) {
            if (n - (i*i) < 0)
                continue;
            ret = min(ret, numSquares(n - (i*i)) + 1);
        }
        mem[n] = ret;
        return ret;
    }
};