23.9. Memoization and Dynamic Programming

In the next few lectures, we will look at a very powerful technique for designing algorithms called dynamic programming.

Dynamic programming is a technique used in algorithm design. It allows us to solve problems by breaking them down into simpler subproblems and storing the solutions to those subproblems to avoid redundant calculations.

Imagine you are trying to solve a puzzle like a jigsaw. Instead of solving each piece from scratch every time, you put aside the pieces that fit together and reuse them later when you work on the larger puzzle. This reuse saves you time and effort, similar to how dynamic programming saves computational resources.

The starting point of dynamic programming is to consider, what we would call inductive definitions. ... for an example in a list or an array, you can consider a sub list or a sub array as a smaller problem.

Inductive definitions allow us to define a function in terms of itself with simpler inputs. For instance, the factorial function can be defined recursively, where factorial of n is n times factorial of n minus one. Similarly, for sorting algorithms like insertion sort, we can sort a list by sorting a smaller portion and then inserting an element.

Think about preparing a meal. You first prepare the individual ingredients (like chopping vegetables), which can be seen as solving smaller problems, and then combine them to create the final dish. This way, you are using simpler tasks (base cases) to reach the overall goal.

What such inductive definitions exploit is what is sometimes called the optimal substructure property. ... in particular to this sub problem is of same type, then it is computing the same type of answer.

The optimal substructure property means that the solution to a problem can be constructed from solutions to its subproblems. For instance, the solution to the factorial problem depends only on the factorial of smaller numbers. This property is crucial for dynamic programming because it allows us to build a complete solution from partial ones.

Consider building a Lego structure. Each smaller section of the structure is built independently and then all sections are put together to form the complete building. Each section must be built correctly, as their correct construction will ensure the whole structure is stable.

Now, in general one could think of any segment X i to X j to sort as a sub problem of sorting...

In algorithms like merge sort, we break the array into segments and sort those segments individually. These sorted segments are then combined to get the final sorted array. Each segment acts as a subproblem that contributes to solving the overall problem efficiently.

Imagine cleaning your house. You don’t clean the entire house at once; instead, you tackle each room one at a time. Each room represents a smaller problem, and once you finish each one, your entire house becomes clean.

So, now let us look at a problem that we are seen before in the context of greedy algorithms. ... the goal is to maximize the number of bookings not the length of the bookings, but the number of bookings.

Dynamic programming differentiates itself from greedy algorithms. In a greedy strategy, you might make a locally optimal choice (like scheduling the earliest finishing booking) without considering the global optimum. Conversely, in dynamic programming, we evaluate all possibilities by defining subproblems to find a solution that optimizes the overall outcome.

It’s like planning a road trip. A greedy strategy might have you take the shortest route at each turn, leading you into unexpected detours or closures. A dynamic programming approach would let you consider the entire journey, evaluating the best route that avoids issues despite being longer at certain points.

So, the whole problem with this approach is that the inductive solution can give rise to the same problem at different stages. ... the goal of dynamic programming is to avoid this wastefulness.

Memoization is a technique that involves storing the results of expensive function calls and reusing them when the same inputs occur again. This prevents repetitive calculations and enhances efficiency, especially in recursive algorithms.

Imagine studying for a test. Instead of repeatedly looking up the same information in your book for every study session, you create a flashcard with the important facts. You then review the flashcard, saving time and effort in your study process.

... dynamic programming will then be a way to avoid doing this recursive calls altogether. ... we will look at these two techniques, the next couple of lectures.

Dynamic programming can process problems in a non-recursive manner by systematically resolving all subproblems and storing their solutions. This approach utilizes a table to store results, making it effective for problems with overlapping subproblems.

Think of an architect designing a large building. Instead of continuously revisiting the same problems (like calculating the weight capacity of different materials), they create a concrete plan (or table) that documents the results of each decision, thus ensuring consistent and efficient building practices.

--