Perfect Squares

1보다 큰 정수 n이 주어지는데 이 때 n을 perfect square들로 만들 때 최소 개수를 구하는 문제

perfect square는 정수의 제곱 수들을 말한다.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

class Solution {
public:
    int numSquares(int n) {

        int table[10000]{[0 ... 9999] = numeric_limits<int>::max()};
        table[0] = 0;
        table[1] = 1;

        vector<int> candidate{1,};
        int power{};
        for (int i = 2; power <= n; i++)
        {
            power = i * i;
            if (power == n)
            {
                return 1;
            }

            table[power] = 1;
            candidate.push_back(power);
        }
        
        for (int i = 2; i <= n; i++)
        {
            if (table[i] == 1)
            {
                continue;
            }

            for (int j = 0; candidate[j] < i; j++)
            {
                table[i] = min(table[candidate[j]] + table[i - candidate[j]], table[i]);
            }
        }

        return table[n];
    }
};