LeetCode 279. Perfect Squares Explanation and Solution

Subscribe and turn on "All notifications" for my channel!

Thanks in advance. :D

Happy coding every day!

Note:
Compared to Coin Change and Integer Break.
Classic DP pattern. Make sure you are familiar with them.
#LeetCode #Algorithms #DynamicProgramming

[psn]

I have been watching your videos lately. It has helped me tremendously. Thanks a lot. Happy interviewing !

[BrijeshPatelEngineer]

at 2:57 what you means by pub integer ?
trying to understand why need n+1 on line 8.
thanks in advance.

[harshalpatil]

i just dint understand one small part why did we use dp[ i - j* j] +1 instead of dp[i - j * j]

[mihirtrivedi]

i generally liked your videos but this one went over my head

[princeshah]

Curious r u solving this problem in space repetition manner bcoz I
Noticed u solved it 2 days then 18 days ago?

[gustavoy]

This problem is almost the same as "Coin Change" to find the minimum number of coins for a given amount. The hardest part is figure out that it is a dynamic programming problem.

[zhenwang]

Thanks for the explanation! But I am confused about why translating the same code to JavaScript doesn't work. Could you help me with it?

/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
let x = Math.sqrt(n)
let dp = Array(n).fill(1);


dp[0] = 0;
dp[1] = 1;
console.log(dp) // until this step, the dp array is the same as yours


for (var i = 1; i <= n; i++) {
for (var j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);

}
}

return dp[n];

};

[hyli]

这道题这样做复杂度稳定在O(n * sqrt(n))，至少需要做普通的剪枝操作，比如
j从i的平方根（需要取整）开始j--，这样的话idp[i] == 1 or dp[i] == 2， break内循环。

[perlaz]

Clear explanation. Very intuitive. Thank you!

[changshengwu]

The explanation is very succinct. It would be better with a BFS solution

[arghadeepsahakiit]

thanks a lot i admire your effort and follow your videos regarding any doubts on leetcode.

[jiaweiyang]

solution is clear, but got a tle in python solution

[raghuveernaraharisetti]

note: this approach throws TLE for python

[rangermaverick]

You can't explain a problem by starting straight away coding because you did it already