Search⌘ K
AI Features
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Solution Review: The Rod Cutting Problem

Explore various methods to solve the rod cutting problem, including simple recursion and dynamic programming approaches. Understand the concepts of optimal substructure and overlapping subproblems, and learn to optimize solutions with memoization and tabulation to improve time and space efficiency.

We'll cover the following...

Solution 1: Simple recursion

Python 3.5
def rodCutting(n, prices):
  if n<0:
    return 0
  max_val = 0
  for i in range(1,n+1):
      max_val = max(max_val, prices[i-1] + rodCutting(n - i, prices))
  return max_val
print(rodCutting(3, [3,7,8]))

Explanation

The idea of this algorithm is to exhaustively find the most optimal cuts from every combination of cuts. We do this by making recursive calls with all possible values of length and choosing those that give us the highest revenue (lines 5-7).

The crux of this algorithm is in line 6. We make recursive calls for each possible length of the piece (i); the updated value of n now is i units smaller. Once this result is evaluated, we add this length’s price and find the max.

The visualization below shows a dry run of this algorithm.

Time complexity

Can you think of the number of combinations of cuts for a rod of length n? It is 2n−12^ ...