0% completed
In the brute-force solution, why '+1' is added to result ? if(result != Int...
Lucifer
Mar 4, 2022
In the brute-force solution, why '+1' is added to result ?
if(result != Integer.MIN_VALUE){ c1 = result + 1; }
0
0
Comments
Design Gurus4 years ago
+1 is for counting the ribbon-cut of the current function call.
We recursively called to get the count of the cuts for the remaining length: (total - ribbonLengths[currentIndex])
Result is assigned the value from the recursive call.
To count the cut of the current ca...
Lucifer 4 years ago
Okay so, adding '+1' to the current function makes sense in this problem.
However, for other problems that follow Unbound Knapsack pattern like Coin change, why '+1' is not added?
Lucifer 4 years ago
I'd really appreciate if you could answer this question.
Design Gurus4 years ago
This is a good question. DP is hard, but these brute-force solutions definitely teach recursion which is an important concept and quite useful. Best to practice recursion.
Now to your question.
Every problem is different.
Over here, we want to find the number of 'cut...
Lucifer 4 years ago
thank you, your detailed response is much appreciated.
On this page