Understanding the Problem Statement

Problem Link: https://leetcode.com/problems/integer-break/

The problem states that given a number, if we express that number as a sum of K integers, where K>=2, what could be the maximum product that we can get as a result of such expression.

For example:

Number = 10

Now, 10 can be expressed as a sum in the following manner
10 => 1 + 9
10 => 2 + 8
10 => 3 + 7
.
.
10 => 1 + 1 + 8
10 => 2 + 3 + 5
.
.
.
10 => 2 + 3 + 4 + 1
10 => 2 + 2 + 3 + 3

Out of all such expressions, we need to find the maximum product that we can get by multiplying the numbers present in the expression.
If you manually write down all the expressions, then you could find that the max product that you can get is 36 ( 2 + 2 + 3 + 3 = 10)

Solution:

If you think in terms of the number of arithmetic expressions that could be generated for a particular number, then the value of that is HUGE and would just make you overwhelmed.

Instead think of what should you actually be doing, which is building up the number.
for example, if we start with a lower value number, let's say 3
Then 3 could be expressed as
3 => 1 + 2
so, the max product that you get with 3 is 2 (1 * 2)
Now for 4
4 => 1 + 3 ( let this be "a")
4 => 2 + 2 ( let this be "b")

if you look carefully, you actually are interested in 1 * maxProduct( 3 ) [ Which is the max product that you get if the number was 3 ]
In the second case, you are basically calculating 2*maxProduct(2)

But the final answer that you want is max ( a, b ) which is the max value that you can get post calculating the expression a and expression b

Now, this is simple enough for 4, because 4 has only 2 forms of expressions.
But if you take larger numbers there might be many expressions involved for you to consider, irrespective of which, the crux remains same, which is:
for every number, you are traversing through all possible outcomes of summing that up, and calculating the max product for every instance.
which when put through code, gives something like this

def maxProduct(number):
    ans = number # minimum that the answer can take is the number itself
    for i in range(1, number):
        ans = max(ans, i* maxProduct(number-i))
    return ans

If you try dry running the above peice of code with the value 4, you should be getting the right answer.

Once our main crux function is completed. We can just plug it in and submit the solution.

class Solution:
    def integerBreak(self, n: int) -> int:
        @cache #this is inbuilt memoization in python 
        def maxProduct(n)->int:
            ans = n
            for i in range(2, n):
                #nonlocal ans
                ans = max(i*maxProduct(n-i), ans)

            return ans 

        if n<=3:
            return n-1

        return maxProduct(n)

If you kinda understood the solution up until now, then congratulations! You just solved a Dynamic Programming Problem!