What is Dynamic Programming?

Dynamic Programming is a process of memoising values that are already known to solve unknown problems. Lets understand with the help of some known examples.

To understand if a problem is a DP problem. We ask the following Questions

1. Does an Optimal substructure exist? Is the problem recursive in nature?
2. Is there an Overlapping subproblem in the solution?

How to Approach a Dynamic Programming Problem?

1. Top Down (Recursive + memoization): Start with a bigger problem and recurse to reach a smaller problem whose answer we already know (Base Case)
2. Bottom Up (Iterative): Start with the smaller problem and solve the bigger problem iteratively.

We shall look more into these approaches by studying the Fibonacci Sequence

What is Memoization

• In Dynamic Programming we use a concept called memoization. Memoization is a technique to store an already known solution to a pre encountered problem in some data structure. If the same problem is encountered, we shall just retrieve the solution from the data structure without further processing costs.
• *Memoisation is useful iff number of states that you had to compute > number of unique states

In case of fibonacci, the number of states is in the $O(2^n)$ while the number of unique states is in the $O(n)$. Therefore fibonacci is better solved using Memoization

Lets approach the fibonacci problem using dynmamic approach.

Approach:

1. Find the Elements of Choice to reach state $f(n)$: To reach state $f(n)$, we need the elements $f(n-1)$ and $f(n-2)$. Therefore we know the elements of choice.
2. Find a way to represent state $f(n)$: state $f(n)$ can be represented by the Equation $f(n)=f(n-1)+f(n-2)$
3. Write the Recurrence Relationship: Here, $f(n) = f(n-1)+ f(n-2)$
4. Find the state that will give the final answer: Here the n'th state gives the final answer.