2.a) Perfect squares problem using dynamic programming

In this video on dynamic programming, I have discussed about perfect squares problem, in which we have to form a number using the sum of squares of natural numbers, such that it is achieved in minimum numbers

Practice questions:

I hope you liked my video, do subscribe to my channel to get the updates of my latest uploads.

#datastructure #algorithm #interviewquestions #placement #internship

[tombrady]

I like your questions in the playlist it is better than me trying random problems and wasting my time.

[ankitkumarmishra]

TOP DOWN APPROACH:

class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, 0);
return recursive_approach(n, dp);
}
int recursive_approach(int n, vector<int> &dp){
if(n<=1)
return max(0, n);

if(dp[n]==0){
dp[n]=INT_MAX;
for(int i=1;i*i<=n;i++){
dp[n]=min(dp[n], recursive_approach(n-i*i, dp)+1);
}
}
return dp[n];
}
};

[sachinsharma]

Thanks for such lucid and smooth explanation.Hope you complete this dp playlist soon.

[DragoonBlod]

We can also think of this problem as Unbounded Knapsack problem considering we have a capacity of N & squares are in unlimited query, This is a space optimized approach of that soln

[abhishekvishwakarma]

Amazing explanation: One request Time and space bata diya karo bhai 😅 waise iska Time: O(n*(n^1/2)) hoga and space O(n)

[coderom]

in this problem Recurrence Relation Click hee nahi hua. I didn't got how dp is storing no. of squares. I re-watched it still not
Any Suggestion
I LIKE BOTTOM UP APPROACH