Given an integer "l" denoting the length of a rod, the task is to cut the rod in such a way that the cut length of the rod segment each time equals either p, q, or r, and the total number of cut segments must be maximum after all cutting operations.
You need to find the maximum number of segments possible to cut.
Input: l = 11, p = 2, q = 3, r = 5
Output: 5
Input: l = 7, p = 2, q = 5, r = 5
Output: 2
Solutions
Method 1: Recursion
Initially, we have a length "l" present with us.
We'd have three size options to cut from this: we could make a cut of length "p", "q", or "r".
Let's say we made a cut of length "p" , so the remaining length would be "l-p" and similarly with cuts "q" & "r" resulting in remaining lengths "l-q" & "l-r" respectively.
In each recursive call, we will return the maximum of the three choices plus "1".
This "1" is to count the current cut.
Base Condition: If length of the rod (l) is zero, that means the rod is exhausted and can not be divided further i.e. return "0".
On the other hand, if the length of the rod "l" turns -(ve) that means this particular combination is not valid, return the maximum -ve value to omit this on the max(a,b,c) function.
Complexity
The time complexity of this solution is exponential O(3^n).
In addition, O(n) auxiliary space was used by the recursion stack.
Method 2: Memoization (DP)
The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.
We can see that in each recursive call only the value of "l" changes, so we can store and reuse the result of a function(..l..) call using an array.
The array will store a particular state (..l.) if we get it the first time.
Now, if we come across the same state (..l..) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.
Complexity
The time complexity of this solution is (n).
In addition, O(n) auxiliary space was used by the table.