Applying Memoization to Dynamic Programming

Dynamic programming

Dynamic programming is an algorithmic technique that uses memoization to make the execution of recursive calls highly efficient. By caching and reusing the results of a function call, dynamic programming eliminates repetitive recursive calls to functions. So computations that may have exponential time complexity may execute with linear time complexity, thanks to memoization.

In the previous section, we used memoization to compute the Fibonacci number and saw how the technique greatly reduced the computation time. Let’s apply the Memoize delegate we created to solve a well-known problem in dynamic programming—the rod-cutting problem.

Unlike the Fibonacci number, where there’s one number for a given position, a category of problems called optimization problems may have multiple possible solutions. A user may pick one among the possible solutions, but we have to explore the different solutions to facilitate that. Dynamic programming is often used to recursively explore the possible solutions for optimization problems. Let’s explore how our solution in the previous section applies to the rod-cutting problem, which is an optimization problem.

A regular solution

Given prices for different lengths of a rod, the objective of the problem is to find the maximum revenue a seller can make for a given rod length by cutting it. For example, given the prices in dollars, 2, 4, 6, 7, 10, 17, 17, for lengths of 1, 2, …, 7 units (inches or centimeters depending on the units of measure you use), find the maximum revenue for a length of 4 units. If the seller were to sell the rod of length 4 as is, the revenue will be $7. However, if cut into four, each of length 1 unit, the revenue will be $8. Likewise, if the seller cuts it into two equal parts, the revenue will be $8. Cutting into two pieces of length 1 and 3 units, incidentally, will yield the same revenue. Thus, there are three solutions, each yielding the same maximum revenue for length of 4 units. But if further cutting the sub-length of 3 units, for example, into smaller pieces may yield a better revenue, we should explore that as well. Thus, the problem nicely fits into a recursive solution, illustrated in the following pseudocode:

maxPrice(length) =
  max {
                maxPrice(1) + maxPrice(length - 1), 
                maxPrice(2) + maxPrice(length - 2), 
                ...,
                maxPrice(length - 1) + maxPrice(1), price[length]
}

This is a maximum of maximum computation; that is, it takes the maximum price for each combination of cuts that total the length and finds the maximum among them.

A memoized solution

This solution can benefit from memoization. The computation of maxPrice(3), for example, involves computing maxPrice(2) and maxPrice(1). And, in turn, computing maxPrice(2) again involves computing maxPrice(1). Memoization will remove such redundancies in computation. Let’s turn the above pseudocode into Kotlin code. The Memoize delegate used in the following code is the one we created in the previous section.