Dynamic Programming ( DP - 2 )

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 for 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 yesterday 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 , Fn=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 F5 we need to find F4 & F3, to find F4 we need to know F3 & F2, and so on.
    • So here our subproblem is Fn.
  • Step 2: Write down a recurrence that relates to the subproblems.
    • Now from above, we know that to find F5 we need to know F4 and F3. Similarly to find F4 we need to know F3 and F2, and so on.
    • So we can write here that Fn = Fn-1 + Fn-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 Fn need to know the value Fn-1 and Fn-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 F1 and F2 here, using which we can calculate F3 and once we know F3 we can calculate F4 by using F3 and F2 and so on.
    • We can calculate Fn = Fn-1 + Fn-2.
    • In the problem, it is given that F1 = F2 = 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 solution to be 
    • N = x1 + x2 + x3 + ... + xm
    • Now if we take xm = 1, then the sum for the rest of the number must be equal to Dn-1.
    • Thus, the number of sums that end with 1 are n-1.
    • Similarly, the number of sums that end with x = 3 and x = 4 are respectively Dn-3 and Dn-4.
    • Then the recurrence relation is Dn = Dn-1 + Dn-3 + Dn-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

Comments