Perfect Squares | perfect squares | perfect squares leetcode | leetcode 279

**Complexity Analysis**
Time Complexity: O(n * sqrt(n))

[akshaygoyal]

Check the description section for code and complexity analysis.

[mazhar]

This is an underrated video. It should reach to more people.

[biranchinarayanpadhi]

The last approach was memoization. I dnt think it is purely a DP sution. Because, you are just storing the last newly calculated f(n) and putting it in a a list. Correct me if i am wrong.

[swagatzeher]

So nicely explained.. Kudos to the content creator !

[rajatsemwal]

Simple and precise explanation Akshay. Can you just explain me why you used the dp array and why you needed it in the process?
Thanks and stay safe...

[Ashish-rvwb]

What was the total runtime you got on this one using memoization?
I am using the matrix method similar to the unbounded knapsack problem with the 2D matrix. My solution got accepted but it takes ~500 ms.

[cloud]

This was the best explanation. I can tell you genuinely understood what you are doing. Thanks for sharing, very helpful. Creating a hashtable for caching is same thing as dp array right? Both give constant time access.

[shivankgupta]

Nice explanation especially the recursion part.

[electric]

Can you explain why the DP array has to be n+1 and not just n?

[pranayghosh]

i still dont understand why this question is in queue and bfs card.
i mean how to solve this using a queue

[suhelali]

class Solution {
public:
int f(int n, vector<int >&dp){
if(n==0) return 0;
if(dp[n]!=-1)return dp[n];
int min_value =INT_MAX;
for(int i=1;i*i<=n;i++){
int curr=f(n-i*i, dp)+1;
min_value=min(min_value, curr);
}
return dp[n]=min_value;
}
int numSquares(int n) {
vector<int>dp(n+1, -1);
return f(n, dp);
}
};