Hi all, in the previous article we have discussed the general concept of Dynamic Programming with an example of finding Nth Fibonacci Number.

**Today we will be discussing,**

- Definition of DP
- Steps involved in Solving DP problems.
- Key Observations
- Practice Problems
- Summary

**Definition of DP**

According to Wikipedia, **dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.** It’s very important to understand this concept. Dynamic programming is very similar to recursion. But when subproblems are solved multiple times, dynamic programming utilizes memorization techniques (memo table – “memo name is from memo pads”) to store results of subproblems so that the same subproblems won’t be solved again.

And the previous article we have simplified this as an Equation,

**Dynamic Programming ≈ Memoization + Recursion**

**Steps involved in solving DP problems.**

These are some of the general steps that need to be taken care while solving DP problems

- Define Subproblems
- Write down a recurrence that relates the subproblems
- Recognize and solve the base cases. ( This is also called as initial states (one or more) )

Now let us understand each of the steps from an example.

**Example 1: Calculating Nth Fibonacci Number Fn=Fn-1 + Fn-2, where for n<=2 , F**_{n}=1

_{n}=1

This is the same problem which we have discussed in the previous article, today we will try to understand the above steps from this problem, let’s start

**Step 1: Define Subproblems**- This represents what we have to find to solve the original problem, for example, to find
**F**we need to find_{5}**F**to find_{4}& F_{3},**F**we need to know_{4}**F**, and so on._{3}& F_{2} - So here our subproblem is
**F**_{n}.

- This represents what we have to find to solve the original problem, for example, to find

**Step 2: Write down a recurrence that relates to the subproblems.**- Now from above, we know that to find F
_{5}we need to know F_{4}and F_{3}. Similarly to find F_{4}we need to know F_{3}and F_{2}, and so on. - So we can write here that
**F**Which is our recurrence relation for finding the Fibonacci Numbers?_{n}= F_{n-1}+ F_{n-2}.

- Now from above, we know that to find F

**Step 3: Recognise and solve the base cases.**- Now to find the value of F
_{n}need to know the value F_{n-1}and F_{n-2}i.e. we should know the previous**two**values in order to find the**“third”**value. - So we need two base case one for F
_{1}and F_{2}here, using which we can calculate F_{3}and once we know F_{3}we can calculate F_{4}by using F_{3}and F_{2}and so on. - We can calculate F
_{n}= F_{n-1}+ F_{n-2}. - In the problem, it is given that F
_{1}= F_{2}= 1 which are the base cases or initial states.

- Now to find the value of F

- After going through all the steps we have defined subproblems, we know the recurrence relation and base case which can be implemented like this in a bottom-up fashion.

**Example 2: Given N>=1, find the number of different ways to write N as a sum of 1, 3, 4.**

In this we need two find number of ways in which we can write given number a sum of 1, 3, 4. for example, let **N = 5**, then we can write 5** = 1 + 1 + 1 + 1 + 1** (or) **5 = 3 + 1 + 1 **(or)** 5 = 1+ 3 + 1 **(or) 5** = 1+ 1 + 3** (or) **5 = 4 + 1 (or) 5= 1 + 4**.

That is we have **6** ways to write **5** as a sum of **1, 3, 4**. Now let us generalize this,

**Step 1: Define Subproblems**- Let Dn be the number of ways to write N as a sum of 1, 3, 4.

**Step 2: Write down a recurrence that relates to the subproblems.**- Now to find the recurrence relation let us consider any one of the solution to be
- N = x
_{1}+ x_{2}+ x_{3}+ … + x_{m} - Now if we take x
_{m}= 1, then the sum for the rest of the number must be equal to D_{n-1.} - Thus, the number of sums that end with 1 is
**n-1**. - Similarly, the number of sums that end with x = 3 and x = 4 are respectively D
_{n-3}and D_{n-4}. - Then the recurrence relation is
**D**_{n}= D_{n-1}+ D_{n-3}+ D_{n-4}

**Step 3: Recognise and solve the base cases.**- D0 = 1
- D1 = D2 = 1
- D3 = 2 (i.e. 1+1+1 and 3 )

- Now from the recurrence that we have got, we can say that this is also similar to that of Fibonacci number’s recurrence relation.

**Key Observations**

These are some of the key observation which I have learned by solving **Dynamic Programming Problems**. They are

- Every DP problem can be expressed in the form of a Recurrence Relation.
- Every DP problem can be represented in the form of a Tree.
- The bottom-up approach to implementation is more efficient than top to bottom.
- Most of the DP problems can be solved using the Greedy Algorithm Design technique.

**Practice Problems**

**Summary:**

Today we have discussed the steps involved in solving DP problems. These are

- Define Subproblems
- Write down a recurrence that relates the subproblems
- Recognize and solve the base cases. ( This is also called as initial states (one or more) )

Then we have solved two problems from scratch using the above 3 steps. With this, we complete the theory perspective of Dynamic Programming.

From the next article, we will explore **different techniques of solving the DP problems by solving problems**.

If you have some **content OR material** related to this **OR there is an error** then do share them through the comment section for which we will be thankful to you.

Thank You