Integer Break - Dynamic Programming - Leetcode 343 - Python

0:00 - Read the problem
1:52 - Recursive Solution
10:18 - DP Solution

leetcode 343

#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[NeetCode]

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

[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.

[irarose]

I'm so happy your chanel has sponsors💟

[tomtom-wvhc]

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.

[krzysztofsobocinski]

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.

[CloseToNature-Palamou]

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

[ngneerin]

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

[AR-yrov]

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

[amateursoundz]

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

[CS_nb]

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

[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?

[tempregex]

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.

[alonalon]

@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?

[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.

[kentsang]

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

[adityarajora]

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],

return maxBreakProductOfNum[n]

[sushantrocks]

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

[jorkhachatryan]

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

[sidazhong]

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

[AhmadRizviYT]

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