Perfect Squares Leetcode 279

#include <bits/stdc++.h>
using namespace std;
/*
QUESTION = https://leetcode.com/problems/perfect-squares/

*/
int getMinSquares(int n, vector<int> &memo){
    //base case
    //if n == 0, min steps needed to reach 0 is 0
    if(n == 0){
        return 0;
    }
    if(memo[n] != -1){
        return memo[n];
    }
    int minSteps = INT_MAX;
    //level = each N
    //options = values upto sqrt(N)
    for(int i = 1; i * i <= n; i++){
        minSteps = min(minSteps, 1 + getMinSquares(n - (i * i), memo));
    }
    return memo[n] = minSteps;
}

int main() {
    // your code goes here
    int n;
    cin >> n;
    vector<int> memo(n + 1, -1);
    cout << getMinSquares(n, memo) << '\n';
}