Perfect Squares Dynamic Programming | Leetcode 279 Solution in JAVA

NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. Here you will know about Perfect Square Problem. In this question :

1. You are given a number N.
2. You have to find the minimum number of squares that sum to N.
3. You can always represent a number as a sum of squares of other numbers.
For eg - In worst case N can be represented as (1*1) + (1*1) + (1*1)..... N times.

#dynamicprogramming #leetcode #perfectsquares

[ujjwalgupta]

This is the best explanation for this question I have got till now. Thank you.

[sudhanshukumar]

I previously had a solution of T= O(n^2) thanks for this approach seems like T=O(nlogn) approach 🙏🙏

[florakunjumon]

Awesome explanation. Dynamic programming seems easier than Recursion for me

[faizanali-gryx]

Extraordinary explanation ❤️❤️❤️
🔥🔥🔥🔥🔥🔥

[balramchoudhary]

thanku sir
your explanation is very easy

[overlordcoding]

Sir, Thank you so much for this video. It is very easy to understand here.

[VishalSingh-gmqj]

Sir aap ki video ka subah se wait krte h please sir no of video thoda badha dijiye sir🙏🙏

[ishanpatni]

Please keep on going and keep up the good work sir!!!

[zaidshaikh]

Amazing explanation👏. Took me an Entire day to debug the logic still didn't got it right

[live_study_with_me]

Ye 01 knapsack ka variation hai kya ?

[factswithai]

As i always say "East or west, sumeet sir is the best"

[alokesh]

Sir if possible please discuss the recursive solution before getting on to the DP part...

[Entertainment-byci]

Sir, it can be solve by solution used in "Coin Change" problem also

[utkarshsharma]

we can also handle 0, 1, 2 case explicitly to save time

[ritiktwopointo]

i think i can now say, that tabulation makes things really easy.

[mickyman]

sir how we would get this tabulation insight, only brute force recusrion came to my mind

[gauravbhansali]

Hello sir, Thank you for the videos..
I am facing some issues in pepcoding ide(c++) even though my logic is correct...sometimes it shows compilation error and sometimes compliation time limit exceeded...and sometimes gives correct output ..but when I submit, it doesn't fix this issue...it will be very beneficial ...thank you

[animatoristu]

I have a question,
Why are you checking for (line 16) dp[rem ]<min before adding 1 (for the step we currently took)? Why not check after adding 1 ?
Ex- int newCount = dp[rem]+1;
if(newCount<min){
min= newCount;
}

[wecan]

correct solution in c++
class Solution {
public:
int numSquares(int n)
{
if(n<=3)
{
return n;
}
int dp[n+1];
dp[0]=0;
dp[1]=1;
for(int i=2;i<=n;i++)
{
int mn=INT_MAX;
for(int j=1;j*j<=i;j++)
{
int rem=i-j*j;
if(dp[rem]<mn)
{
mn=dp[rem];
}
}
dp[i]=mn+1;
}
return dp[n];

}
};

[tanmaychaudhary]

sir is talking about LIS . will anybody tell me what is this LIS???