Rod Cutting Problem - Solution Using DP

The problem with the previous approach

Because we implemented the solution using Recursion in the previous lesson, we got exponential time complexity. By visualizing the recursion tree, we can easily confirm that the subproblems are overlapping, and thus we can use dynamic programming to solve this problem. Let’s first look at the recursion tree for RodCut(6), RodCut(5), RodCut(4), and RodCut(3) only to confirm that the subproblems are overlapping.

Solution: