Perfect Squares - Dynamic Programming / Dynamic number of subproblems

Problems
1

https://algo.monster/problems/perfect_squares

2

My two cents

using namespace std;
int dfs(int n, vector<int> & dp) {    
    if(n == 0) return 0;
    if(dp[n] != 0) return dp[n];
    dp[n] = n;
    for(int i = 1; i * i <= n; i++) {
        dp[n] = min(dp[n], 1 + dfs(n - i * i, dp)); 
    }
    return dp[n];
    
}
5

This basically the same problem as “Coin Change”, where the set of perfect squares less than n are the coin values and n is the amount.