Integer Break - Dynamic Programming - Leetcode 343 - Python

[@NeetCode]

Let me know if you prefer drawing & code at the same time or separately!

[@TheElementFive]

Same time!

[@yamibakura7491]

Doing it side by side gives an experience of how to do it in real interviews. Loved the video, Thanks for explanation!

[@ThiagoTokarski]

same time

[@ROFEL]

Same Time!

[@joyride6062]

Same time

[@hardboiledege]

The reason your DP solution is slower than you expected is that you're doing double the work in your inner loop. Specifically, you can do `for i in range(1, num // 2):` instead of `for i in range(1, num):` because `for i in range(num // 2 + 1, num):` is essentially a repeat of the previous half.

[@sandeepmourya8922]

but then, there will be no overlapping subproblems right??

[@justine-george]

Brilliant

[@irarose3536]

I'm so happy your chanel has sponsors💟

[@CloseToNature-Palamou]

For the inner for loop we can minimize the loop by only executing till num//2+1 to avoid duplicate calls / calculation .

[@krzysztofsobocinski2207]

Great explanation, although I preferred previous format - first explanation than code. I think the second loop could end earlier at num//2 + 1 because of symmetry.

[@alonebeast5310]

yeah i was thinking the same thing and searching if someone ask that😃

[@niallmandal2249]

@@alonebeast5310 its actually not symmetry. As the numbers get larger, the sum is made up solely of 2s and 3s.

[@ytbcmt4686]

Prefer the drawing first!!

[@tomtom-wv3hc]

Amazing content as usual :) Could you please draw first to get a wider picture of a problem. First, we need to create a mental image then we can code.

[@sparshbatta7070]

No, this method is better so that we may have a clear image of each and every step of the code and the whole intuition of why we need what we did at each stage!

[@AR-yr5ov]

This is a really confusing problem, I think understanding what they want is the hardest part.

[@ngneerin]

There is a O(c) solution for this. Ceil(Num/2) × 2s (or 3×2s if remaining is odd)

[@deepaksingh7042]

I dont agree. Please corect me if I am wrong Lets consider for n=8, Max product is = 2*3*3 = 18 But according to your approach it is Ceil(8/2)*2s = 2*2*2*2 = 16 which is less than optimal answer 18

[@amateursoundz6262]

After doing a ton of CP with C++, it is pleasant to look at python code

[@CS_n00b]

Max product for a certain k would occur when the integers are as close to equal as possible

[@ROFEL]

368: Largest Divisible Subset

[@skyandshoe]

Thank you for the solution !! It was very intuitive. I do have a question tho, if dp was an array rather than a dictionary it actually significantly slows down the time complexity. However, we are only obtaining the element so shouldn't the time of retrieval both be O(1) for both array and dictionary? Why the choice of dictionary?

[@AhmadRizviYT]

if you implement with array you get collision error, but in dictionary you dont have to solve that

[@shensean1784]

Thanks. I will init up to 3 😁

[@srinadhp]

I prefer the old style. Again, a bit of confusing problem and the way you explained is great as usual. I still didnt get it, need to watch couple more times.

[@NeetCode]

Appreciate the feedback sir!

[@tempregex8520]

I actually am still finding it a little difficult to wrap my head around when input is n=2, and when the subproblem has n=2 i.e. why is dp[2]=2 ? i guess this is a very tricky edge case, i mean, I would have liked to handle it as a base case had the input number n =2, then i would return 1, but when 2 is a subproblem, then we would return 2 only and not 1. That part is a little confusing to me tbh.

[@sushantrocks]

Choices from [1,2,3,4,...,n-1] => coin change-esque?

[@kentsang9376]

Please make more dynamic programming videos!!!! They are so good

[@alonalon8794]

@NeetCode 4:05 why you can leave the 3 as it is? you must break it up into at least 2 elements. Or I'm wrong?

[@berkeevrensevdi1788]

The question says that input must be broken into the sum of k positive integers, where k >= 2. When you break up 4 into two pieces as (1, 3), it means that you select 1 as the first number and selecting 3 as the second number without breaking into pieces obeys the rule of k >= 2. However, if the actual input were 3, then you can not select 3 directly because k would be equal to 1 and it would break the rule of k >= 2. So, you can always select the number itself, if the number is not the actual input.

[@soumyajitchatterjee5822]

good explanation!!!@@berkeevrensevdi1788

[@adityarajora7219]

def integerBreak(self, n: int) -> int: maxBreakProductOfNum = list(range(n+1)) maxBreakProductOfNum[n] = 0 for i in range(n+1): for j in range(i): maxBreakProductOfNum[i] = max(maxBreakProductOfNum[i], maxBreakProductOfNum[j]*maxBreakProductOfNum[i-j]) return maxBreakProductOfNum[n]

[@AsifIqbalR]

Notification gang ✌

[@jorkhachatryan317]

I know it's about coding, but I found a math solution that is easier to understand and to code.

[@AhmadRizviYT]

i saw the solution but i coded it in c++... so its not full cheating :)

[@sidazhong2019]

There is just no way to figure out the true DP solution directly. This problem is hard.

[@bantyK]

Drawing first please. I like to understand stuff first and then code it afterwards on my own. I think its more helpful that way

[@dekumidoriya-qi2is]

this gives wrong answer for n == 2 and n == 3, as for 2, 1*1 = 1 and for 3 , 1*2 = 2 but for all other cases it works

[@sangeethreddychejerla6527]

Hello sir,I want help how can I learn logic for programming and I want learn python and I am self taught learner

[@sergiobost4891]

How do you join the discord server

[@NeetCode]

Can join here: discord.gg/ddjKRXPqtk

[@jackie0315]

but your code here only breaks an integer n into two pieces? val = dp[i] *dp[num-i]? what if the optimal break has more than 2 pieces

[@berkeevrensevdi1788]

dp[i] and dp[num-i] hold max values and they consist of at least one piece. For example, if the input were 8, dp will be {1 : 1, 2 : 2, 3 : 3, 4 : 4, 5 : 6, 6 : 9, 7 : 12, 8 : 18}. Here dp[8] = dp[6] * dp[2] = 18 -> dp[6] = dp[3] * dp[3] = 9 -> dp[3] = 3. So actually dp[8] is 3 * 3 * 2.

[@shrinilthakkar4589]

Not the most optimized solution. It can be solved in constant time. Just try to break n into 2 equal halves. The product of those numbers will be the max possible products. If n is even, for example, n=6, max product = n/2*n/2 i.e. 3*3 = 9 If n is odd, for example, n=5, max product = int(n/2)*int(n-n/2) i.e. 2*3 = 6

[@nehaagrawal25]

I don't agree. Let's say, If n is even, for example, n=8, n/2*n/2 i.e. 4*4 = 16 which is not equal to 18 (max product for 8).

[@akhileshsonkar2061]

First 😎