23.9. Memoization and Dynamic Programming

Try these first

1. 1.

   What is dynamic programming?

   Hint

   Think of how recursive functions work.

2. 2.

   What is the base case in the factorial function?

   Hint

   Consider what the output should be for zero!

3. 3.

   What does dynamic programming generally focus on?

   • Recursive approaches
   • Iterative processes built on stored results
   • Sorting algorithms only

   Hint

   Think about how dynamic programming reduces repeated calculations.

4. 4.

   True or False: Memoization is a technique that stores previously computed results.

   • True
   • False

   Hint

   Consider whether ideas have been repeated in your study.

5. 5.

   Given an array of weights and values, determine how to maximize value with a weight limit using dynamic programming.

   Hint

   Think of how you can compute values iteratively based on smaller weight limits.

6. 6.

   Devise a dynamic programming algorithm to find the longest common subsequence of two strings.

   Hint

   What relationships can you derive between characters of the strings?