How to solve a Dynamic Programming Problem

October 18, 2024

How to solve a Dynamic Programming Problem 

Dynamic programming is a special kind of programming to find an optimised solution to a problem which demands optimal answers, like maximum or minimum in a non greedy approach. This is an article on how to solve Dynamic Programming problems in a methodical way.

 
How to solve a Dynamic Programming Problem | PrepInsta
How to solve a Dynamic Programming Problem
What is Dynamic Programming

What is Dynamic Programming?


The word “Dynamic” describes something as continuously changing. In a coding problem, if you need an optimal result, like minimum or maximum or something like that, you have two types of algorithmic paradigms.

  • Greedy Approach, where you sort the total thing with some logic and then choose the best answer for every step.
  • Dynamic Programming, where you keep the data as it is, and try to find all the possible ways to find the optimised answer.

Algorithm with example

Let us discuss this with a coding problem. We all know about the problem of Length of Longest Common Subsequence. This goes like, let us say there are two strings, and we have to find what is the length of the longest common subsequence possible made of the characters that are present in both of the strings in the same order. So let us say, the words are “PREPINSTA” and “ENCODING”. So word1 is with length 9 and word2 is length 8. When we ask the Length of Longest common subsequence of word1 and word2, we actually mean to find the length of that of word1 till that’s last index and word2 till that’s last index.

 

  • Identify problem: First we have to recognise the problem is DP. Here we know the problem has Optimal Substructure property

  • Identify problem category: There are some variables of the most used algorithms in DP, like knapsack 0/1, LCS etc. We have to understand the variable if possible. This is standard LCS kind of problem.

  • Find the recurrence: We can find the recursive notation or the equation where the results in the upper index depend on the result of the lower index. Here we can see the recurrence for two different logic. If word1 [Index1] and word2 [Index2] are same, then return 1+ LCS(word1, word2, Index1-1,Index2). Else return the maximum of LCS (word1, word2, Index1-1,Index2-1) and LCS (word1, word2, Index1,Index2-1).

  • Identify the base cases: Base cases means where the code terminates. Here the base condition will be if Index1 or Index2 is less than 0.

  • Iteration VS Recursion: We have to decide if we can implement it iteratively or recursively. Also if you can find out the optimal substructure property in your problem you can put memoization or tabulation and solve the problem by solving its subproblems. Here we are performing recursion.

  • Space Optimization: Adding memoization or Tabulation. Here memoization is added.

The code to implement this:

Run 
#include <bits/stdc++.h>
using namespace std;

map< int, map< int,int>> m;

int LCS(string word1, string word2, int Index1, int Index2)
{
    if(Index1 <0 || Index2 <0) return 0;
    if(m[Index1][Index2]) return m[Index1][Index2];
    if(word1[Index1]==word2[Index2]) return m[Index1][Index2] = 1+ LCS(word1,word2,Index1-1,Index2-1);
    
    return m[Index1][Index2] = max(LCS(word1,word2,Index1,Index2-1),LCS(word1,word2,Index1-1,Index2));
}

int main()
{
    string word1 = "PREPINSTA", word2 = "ENCODING";
    cout<< (word1,word2,word1.length()-1,word2.length()-1);
}

Output:

3