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 ...