Description

Submission

class Solution {
public:
    int numSquares(int n) {
        vector<int> perfectSquares;

        for(int i = 1; i <= sqrt(n); ++i) {
            perfectSquares.push_back(i*i);
        }
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;

        for(int i = 1; i <= n; ++i) {
            for(auto x: perfectSquares) {
                if(i - x >= 0) {
                    dp[i] = min(dp[i], dp[i-x]+1);
                }
            }
        }

        return dp[n];
    }
};