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^{n-1}! For a rod of length nn, at each position, we have two choices. Either we can make a cut, or we can leave it as it is. All combinations are bounded by O(2^n) as is the time complexity of this solution.

Solution 2: Top-down dynamic programming

Let’s see if this problem satisfies both the properties of dynamic programming.

Optimal substructure

We want to find the optimal answer for a rod of length n, and we have optimal answers to all the subproblems, i.e., rods of length n-1, n-2, … , 2, 1. We can find the maximum of all the subproblem’s results plus the price of the rod length that remains along with that subproblem. The following would be the equation for finding the optimal cut’s revenue for a rod of length n.

RC(n)=max(RC(n−1)+price(1),RC(n−2)+price(2)  ...  RC(1)+price(n−1))RC(n) = max (RC(n-1) + price(1) , RC(n-2) + price(2) \ \ ... \ \ RC(1) + price(n-1))

Thus, if we have answers to the subproblems of rods of length n-1, n-2 … 2 and 1, we can construct the solution for the rod of length n by only using these results.

Overlapping subproblems

By looking at the visualization above, you can already see one overlapping subproblem. For bigger inputs, this overlap will increase substantially.

This calls for the memoization of results! Let’s look at the top-down implementation of this algorithm.

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

Explanation

You have seen this many times now: there’s nothing fancy here! Before evaluating a result, we check if it is already computed and available in the memo (lines 4-5); in this case, we do not need to evaluate it. If we have to evaluate it, we simply store results in the memo for future reuse (line 9).

Time and space complexity

Each problem depends on the smaller subproblems; to evaluate rodCutting(n), we need the answer to rodCutting(n-1), rodCutting(n-2), and so on until rodCutting(1). Thus, the time complexity would be O(n2^2). Moreover, we can only have n unique subproblems, making the space complexity of this algorithm O(n).

Solution 3: Bottom-up dynamic programming

Python 3.5
def rodCutting(n, prices):
  # Create a dp array the size of (n+1)
  dp = [0 for _ in range(n + 1)]  
  # starting from rod of length 1, find optimal answer to all subproblems
  for i in range(1, n + 1):       
    max_val = 0
    # for a rod of length i, we can find what cuts give max answer since we have answer to all smaller cuts
    for j in range(i):            
      max_val = max(max_val, prices[j]+dp[i-j-1])
    dp[i] = max_val
  # return answer to n length rod
  return dp[n]                    
print(rodCutting(3, [3,7,8]))

Explanation

The idea is to start building from the case of a rod of length 1, and then use these results to solve the problems for bigger lengths. The solution to a problem of the rod of length n would not require answers to the problems of rods greater in length than n. Therefore, the for loop at line eight only iterates until i, which is any given length of the rod up to n. We make every possible cut, and for the remaining rod length, we would already have the solution in dp. Thus, we choose the cut that gives the highest possible answers (line 10).

Look at the following visualization for an understanding of this algorithm.

Time and space complexity

Similar to the top-down solution, the time complexity here would be quadratic. You can sense this from nested for loops as well. The intuitive reasoning behind this is that to construct an optimal answer to any subproblem, you require optimal solutions to all the smaller subproblems. Thus, the time complexity becomes O(n2^2). Moreover, since there are n possible subproblems, the size of the tabulation table, dp, would be n, making the space complexity O(n).

In the next lesson, you will solve another coding challenge.