General Steps to Solve any Dynamic Programming Problem

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 of 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

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 F₄ & F₃, to find F₄ we need to know F₃ & F₂, and so on.
• So here our subproblem is F_n.

• Step 2: Write down a recurrence that relates to the subproblems.
• Now from above, we know that to find F₅ we need to know F₄ and F₃. Similarly to find F₄ we need to know F₃ and F₂, and so on.
• So we can write here that F_n = F_n-1 + F_n-2. Which is our recurrence relation for finding the Fibonacci Numbers?

• 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 cases one for F₁ and F₂ here, using which we can calculate F₃ and once we know F₃ we can calculate F₄ by using F₃ and F₂ and so on.
• We can calculate F_n = F_n-1 + F_n-2.
• In the problem, it is given that F₁ = F₂ = 1 which are the base cases or initial states.

• 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 solutions to be 
• N = x₁ + x₂ + x₃ + ... + 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 observations 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

1. Army ( 38E )
2. Tetrahedron ( 166E )

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.

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 & Regards