23.7. Inductive Solution Approach

So, the starting point of dynamic programming is to consider, what we would call inductive definitions. Now, there are many very simple functions which we come across which are inductive. So, we all know that mathematically n factorial is n times n minus 1 factorial. So, we can write an inductive definition of factorial is follows. The base case is when n is 0 and in this case the factorial is 1, so f of 0 is 1. And in general, if we have n greater than 0, then f of n is given by n times f of n minus 1. In other words, we express the factorial of n in terms of the same function applied to a smaller input.

Inductive definitions allow us to define complex functions in a simpler manner. For instance, factorials can be defined using a base case and a recursive case: if n is 0, then f(0) = 1, and for n > 0, f(n) = n * f(n - 1). This shows that the function refers back to itself with a smaller input, which is a core concept in recursion.

Imagine you're building a tower of blocks. If you decide that the base of the tower (0 blocks) is stable on its own, you know that to build a tower of 3 blocks, you simply need to add one block to a tower of 2 blocks. This approach continues with each additional block being added to a smaller tower.

So, here is a very simple way of describing insertion sort. So, if I want to sort n elements, then the way insertion sort does is that of course, there is nothing to sort the base case, then we have done. Otherwise, we look at the rest of the list starting from the second element and we recursively sort it and then we insert the first element into the sorted list.

Insertion sort is another example of an inductive process. The base case occurs when there's only one element to sort (which is trivially sorted). For more than one element, we recursively sort the rest of the list and then integrate the first element into the sorted arrangement. This recursive structure allows for simplifying a complex sort operation by breaking it into manageable pieces.

Think of sorting a deck of cards. You pick up a card and then compare it against the others one by one, placing it into the right spot. If it's just you and one card, you already know that one card is sorted! But as you pick up more cards, you sort them one at a time, fitting them into the right place among those you have sorted already.

What such inductive definitions exploit is what is sometimes called the optimal substructure property. So, what is complicated base means basically is what you expect from an inductive definition that is you solve the original problem by combining solution to sub problems.

Optimal substructure implies that a problem can be broken down into smaller, similar subproblems, whose solutions can be combined to solve the original problem effectively. This trait makes it possible to use recursive solutions, as solving each smaller instance of the problem brings us closer to the final solution.

Consider planning a road trip. You might plan your entire route based on smaller trips between different locations. Each small segment of the trip (like getting from your home to the first stop) is manageable and can be planned separately, which collectively allows you to tackle the entire trip successfully.

So, now let us look at a problem that we are seen before in the context of greedy algorithms. So, we will look at the problem called interval scheduling. So, integrated scheduling said that we had a resource which is available over a period of time and now people will come and make bookings for these resources.

The interval scheduling problem involves allocating resources over time, avoiding conflicts between overlapping requests. By examining the schedule of requests (start and end times), we can determine the maximum number of requests that can be honored without conflicts. This is an example of using inductive reasoning to handle scheduling issues effectively.

Imagine a single conference room where different people request to hold meetings at various times. If two people want to book the room at overlapping times, you need to decide which request to accept and which to decline—like solving a puzzle to fit the maximum number of meetings into the room's timetable without conflict.

The whole problem with this approach is that the inductive solution can give rise to the same problem at different stages. And if we just use recursion as we said before one of the great benefits are having an inductive definition is that you can just write a recursive solution which just mirrors the inductive definition of the problem.

When using an inductive method recursively, we might encounter the same subproblem multiple times, leading to inefficiency. If we do not account for previously solved problems, our approach can become exponentially expensive, as the number of calls grows rapidly with problem size.

Think about trying to find a book in a library by repeatedly wandering the same aisles. If you keep looking at the same shelves over and over, it would take you much longer to find the book you need rather than noting where you have already searched and focusing on new areas. Similarly, solving a problem without accounting for past work can waste time and resources.

So, the goal of dynamic programming is to avoid this wastefulness. So, there are two techniques that we will see, there is technique called memoization, which is a way to build in some cleverness into recursion...

Dynamic programming is a method to optimize recursive solutions by storing previously computed results (memoization). This avoids recalculating solutions for the same subproblems, thus significantly improving efficiency. This technique allows us to use induction effectively while retaining computational speed.

Using a recipe book can be compared to memoization. If you frequently cook the same dishes, jotting down tweaks you made helps you prepare better each time, without starting from scratch. In programming, noting down results of computations allows us to reuse them instead of recalculating, making our algorithms faster.

--