Dynamic Programming Problem: Everything You Need to Know

Dynamic Programming is used to break down a complex problem into smaller chunks and find a solution to the problem effectively. The optimum solution to the core problem depends on the ideal solution to each of the smaller subproblems. In the 1950s, Richard Bellman came up with the concept for the approach. The DP technique only computes the answer once for each subproblem, which saves time by avoiding recalculating it when the same subproblem resurfaces.

When you finish this tutorial, you will be able to comprehend and apply solutions to the most challenging programming problems using dynamic programming techniques.

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

Dynamic Programming Problems - Longest Common Subsequence

You have to determine the length of the longest common subsequence shared by both sequences. A subsequence is a sequence of events that occur in the same order but are not necessarily contiguous.

Algorithm

1. Create a table with the dimensions (x+1*y+1), where x and y are the lengths of strings A and B. 
2. To represent the end of the string, insert a null column and row. Insert zeros in all of the first rows and columns.
3. You will use the logic given below to fill each cell in the table.
4. If the character equivalent to the current row and column matches, add one to the current cell. Draw an arrow to the diagonal cell.
5. If not, use the most outstanding value from the previous column and row element. Draw an arrow to the most significant value cell. If they're all the same, pick one.
6. You must repeat the steps from 3 to 5 until the whole table is filled.
7. The value reflects the length of the longest common subsequence in the final row and column.

Code

int LCS( char *A, char *B, int x, int y )

{

    int L[x+1][y+1];

    int i, j;

    for(i =0; i<=x; i++){

        for(j=0; j<=y; j++){

            if( i==0|| j==0)

                 L[i][j] = 0;

            else if(A[i-1] == B[j-1]){

                L[i][j] = L[i-1][j-1] + 1;

            }

            else{

                L[i][j] = maximum(L[i-1][j], L[i][j-1]);

            }

        }

    }

    return L[x][y];

}

int maximum(int a, int b)

{

    return (a > b)? a : b;

}

Dynamic Programming Problems - Longest Increasing Subsequence

The LIS problem involves determining the length of the longest increasing subsequence within a given sequence. Its contents are arranged in ascending order of increasing length. As an example, the length of LIS for the set {10, 15, 13, 9, 21, 22, 35, 29, 64} is 6 and LIS is the set {10, 15, 21, 22, 35, 64}.

Algorithm

1. First, make a 1D array of size n.
2. Next, you must iterate it for each element from index 1 to n-1.
3. In a nested loop, iterate the elements with indices smaller than the current element.
4. In this nested loop, if the element's value is less than the current element, then assign lis[i] with (lis[j]+1), and vice versa.
5. Finally, you will need to traverse the entire lis[] array to get the maximum element.

Learn the Ins & Outs of Software Development

Caltech Coding BootcampExplore Program

Code

/* lis() returns the length of the longest

increasing subsequence in arr[] of size N */

int lis(int arr[], int N)

{

int lis[N];

lis[0] = 1;

/* Compute optimized LIS values in

bottom up manner */

for (int i = 1; i < N; i++) {

lis[i] = 1;

for (int j = 0; j < i; j++)

if (arr[i] > arr[j] && lis[i] < lis[j] + 1)

lis[i] = lis[j] + 1;

}

// Return maximum value in lis[]

return *max_element(lis, lis + N);

}

Dynamic Programming Problems - Minimum Number of Edits

Given two strings, str1 and str2, do the operations listed below on str1. Determine the smallest number of modifications (functions) needed to convert 'str1' to'str2.'

• Insert 
• Remove 
• Replace

All of the following operations have the same price tag.

Algorithm

1. Create a table to store the results of subproblems.
2. You must fill d[][] in a bottom-up manner.
3. If the first string is empty, insert all characters from the second string.
4. If the second string is empty, erase all characters from it.
5. If the last character is the same, ignore it and recur for the remaining string.
6. If the last character is different, consider all possibilities and find the minimum.

Code

int min(int x, int y, int z) 

{ 

return min(min(x, y), z); 

} 

int editDistDP(string str1, string str2, int m, int n)

{

    // Make a table to keep track of the results of the subproblems.

    int dp[m + 1][n + 1]; 

    // Fill in d[][] from the bottom up.

    for (int i = 0; i <= m; i++) {

        for (int j = 0; j <= n; j++) {

            // If the first string is empty, 

  //you must insert the entire second string.

            if (i == 0)

                dp[i][j] = j; // Min. operations = j  

            // If the second string is empty, 

  //erase all characters from it.

            else if (j == 0)

                dp[i][j] = i; // Min. operations = i  

            // If the last character is the same         

  // and recur for remaining string

            else if (str1[i - 1] == str2[j - 1])

                dp[i][j] = dp[i - 1][j - 1];  

     //If the last character is different, get the minimum.

            else

                dp[i][j]

                    = 1

                      + min(dp[i][j - 1], // Insert

                            dp[i - 1][j], // Remove

                            dp[i - 1][j - 1]); // Replace

        }

    }  

    return dp[m][n];

}

Dynamic Programming Problems - Total Number of Ways to Cover the Distance

If you have a distance 'dist,' count the total number of ways you can cross that distance in 1, 2, and 3 steps.

Algorithm

1. You must make an array of size n + 1 with the first three variables set to 1, 2, and 3, respectively. These are the underlying issues.
2. Make a loop from 3 to n times.
3. Calculate the value of the ith position for each index i using the formula dp[i] = dp[i-1] + dp[i-2] + dp[i-3].
4. Count the number of different ways to go a distance in one direction using the value of dp[n].

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

Code

int print_CountDP(int distance)

{

    int cnt[distance+1];

    // We'll set the base values. There are two ways to cover distances of 0 and 1.

     cnt[0] = 1;

     if(distance >= 1)

            cnt[1] = 1;

     if(distance >= 2)

              cnt[2] = 2; 

    // Fill the count array in bottom up manner

    for (int i=3; i<=distance; i++)

       cnt[i] = cnt[i-1] + cnt[i-2] + cnt[i-3];

    return count[distance];

}

Dynamic Programming Problems - Subset Sum Problem

You’ll be given a set of non-negative integers and a sum value, and you will have to figure out if there's a subset of the supplied set with a sum equal to the total.

Algorithm

1. Create a boolean-type 2D array with the size (arr.size() + 1) * (target + 1) with the type boolean.
2. In the case where there is a subset of elements from A[0....i] that have a sum value equal to 'j,' then the state DP[i][j] holds.
3. To avoid repeating responses from prior cases, you have to make sure the current element is more significant than the "current sum value."
4. You have to examine previous states for the sum='j' OR the value j – A[i], which will assist you in achieving your goal if it is larger than the current total value.

Code

//It will return true if subset of set[] 

//has sum equal to given sum; false otherwise

bool is_subset_sum(int set[], int n, int target_sum)

{

//If set[0..j-1] has a subset with 

//target_sum equal to i then the 

//value of sub_set[i][j] will be true.

bool sub_set[n + 1][target_sum + 1];

// If target_sum is 0, then answer is true

for (int i = 0; i <= n; i++)

sub_set[i][0] = true;

// If target_sum is not 0 and set is empty,

// then answer is false

for (int i = 1; i <= target_sum; i++)

sub_set[0][i] = false;

// we will now fill the subset table in bottom up manner

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= target_sum; j++) {

if (j < set[i - 1])

sub_set[i][j] = sub_set[i - 1][j];

if (j >= set[i - 1])

sub_set[i][j] = sub_set[i-1][j]

|| sub_set[i - 1][j - set[i - 1]];

}

}

return sub_set[n][target_sum];

}

Dynamic Programming Problems - Shortest Common Supersequence 

To determine the smallest string that contains strings 1 and 2 as subsequences, you must first determine the length of the shortest string that contains neither string 1 nor string 2.

Algorithm

1. If the end of the first string is reached, return the second string.
2. If the end of the second string is reached, return the first string.
3. If the last character of X and Y matches, include it in SSC and recur to find SCS of substring X[0…m-2] and Y[0…n-1].
4. If the current cell's top cell has a more significant value than the left cell, find SCS of substrings X[0...m-2] and Y[0...n-1].
5. For substrings X[0...m-1] and Y[0...n-2], get SCS of the current character of string Y.

Code

int superSeq(string X, string Y, int n, int m,

             vector<vector<int> > lookup)

{

    if (m == 0 || n == 0) {

        lookup[n][m] = n + m;

    }

    if (lookup[n][m] == 0)

        if (X[n - 1] == Y[m - 1]) {

            lookup[n][m]

                = superSeq(X, Y, n - 1, m - 1, lookup) + 1;

        }

        else {

            lookup[n][m]

                = min(superSeq(X, Y, n - 1, m, lookup) + 1,

                      superSeq(X, Y, n, m - 1, lookup) + 1);

        } 

    return lookup[n][m];

}

Dynamic Programming Problems - Matrix Chain Multiplication

You will be given a sequence of matrices; your task is to determine the most efficient technique to multiply them together. The problem is not so much with performing the multiplications but with determining the order in which they should be performed.

Algorithm

1. You shall partition the matrix sequence into two subsequences by taking the matrix sequence as a starting point.
2. You must calculate the smallest possible cost of multiplying out each subsequence.
3. You should add these costs and multiply the two result matrices.
4. This process is done for every possible matrix split and minimum.

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

Code

// Function for matrix chain multiplication

int matrixChain(int* p, int i, int j)

{

    if (i == j)

    {

        return 0;

    }

    if (dp[i][j] != -1)

    {

        return dp[i][j];

    }

    dp[i][j] = INT_MAX;

    for (int k = i; k < j; k++)

    {

        dp[i][j] = min(

            dp[i][j], matrixChain(p, i, k)

                     + matrixChain(p, k + 1, j)

                       + p[i - 1] * p[k] * p[j]);

    }

    return dp[i][j];

}

int MatrixChainOrder(int* p, int n)

{

    int i = 1, j = n - 1;

    return matrixChain(p, i, j);

}

Dynamic Programming Problems - Coin Change Problem

Given a value N, you must determine how many ways you may change for N cents if you have an endless supply of S = S1, S2,..Sm valued coins.

Algorithm

1. Since the table is built from the bottom up using the base case 0 value case (n = 0), you will require n+1 rows.
2. Fill in the blanks for the case with a 0 value (n = 0).
3. Fill in the remaining table entries in a bottom-up manner.
4. You have to calculate the Count of solutions including S[j] and excluding S[j].
5. Then you have to find the total of the sum.

Code

int count( int S[], int m, int n )

{

    int i, j, x, y; 

    // We need n+1 rows as the table

    // is constructed in bottom up

    // manner using the base case 0

    // value case (n = 0)

    int table[n + 1][m];     

    // Fill the entries for 0

    // value case (n = 0)

    for (i = 0; i < m; i++)

        table[0][i] = 1; 

    // Fill rest of the table entries

    // in bottom up manner

    for (i = 1; i < n + 1; i++)

    {

        for (j = 0; j < m; j++)

        {

            // Count of solutions including S[j]

            x = (i-S[j] >= 0) ? table[i - S[j]][j] : 0; 

            // Count of solutions excluding S[j]

            y = (j >= 1) ? table[i][j - 1] : 0; 

            // total count

            table[i][j] = x + y;

        }

    }

    return table[n][m - 1];

}

Dynamic Programming Problems - Word Break Problem

You are given an input string and a dictionary of words; you must evaluate whether the input string can be split into dictionary terms.

Algorithm

1. First, you must create a DP table to hold subproblem results. If str[0..i-1] can be split into dictionary words, wb[i] is true, otherwise false.
2. Initialize all values as false.
3. If wb[i] is false, see if the current prefix may change it. "str.substr(0, i)” is the current prefix.
4. If wb[i] is true, find all substrings starting with (i+1) and store their results.
5. If wb[j] is false, update it. The dictionaryContains() parameter takes a substring starting at index I and length j-i.
6. If none of the prefixes worked, then you will return false.

Code

/* A function to verify if a word is in the dictionary. A dictionary is a string array. Using an array of strings for a dictionary is a bad idea. For program simplicity, we used */

int dictionary_Contains(string word)

{

    string dictionary[] = {"mobile","sung","man","mango",

                           "icecream","and","go","i","like","ice","cream",samsung","sam""};

    int length= sizeof(dictionary)/sizeof(dictionary[0]);

    for (int i = 0; i < length; i++)

        if (dictionary[i].compare(word) == 0)

           return true;

    return false;

} 

// A space-separated string can be divided into words, else false.

bool wordBreak(string str)

{

    int n = str.size();

    if (n == 0) return true; 

    // Create a DP table to hold subproblem results. If str[0..i-1] can be split into dictionary words, wb[i] is true, otherwise false.

    bool wb[n+1];

    memset(wb, 0, sizeof(wb)); //we have to initialize all values as false.

    for (int i=1; i<=n; i++)

    {

        // Verify that the current prefix may make wb[i] true. "str.substr(0, i)" is current prefix

        if (wb[i] == false && dictionary_Contains( str.substr(0, i) ))

            wb[i] = true; 

        // If wb[i] is true, we must search for all substrings beginning 

//with the (i+1)th character and save the results.

        if (wb[i] == true)

        {

            // If we reached the last prefix

            if (i == n)

                return true; 

            for (int j = i+1; j <= n; j++)

            {

         // wb[j] if false, update it. can The dictionaryContains() parameter

//takes a substring starting at index I and length j-i.

if (wb[j] == false && dictionary_Contains( str.substr(i, j-i) ))

                    wb[j] = true; 

                // If we reached the last character

                if (j == n && wb[j] == true)

                    return true;

            }

        }

    } 

    // If none of the prefixes worked,

    return false;

}

Become a Certified UI UX Expert in Just 5 Months!

UMass Amherst UI UX BootcampExplore Program

Dynamic Programming Problems - Rod Cutting Problem

You are provided an n-inch rod and a list of prices for all pieces smaller than n. You must determine the maximum value possible by dismantling the rod and selling the parts.

Algorithm

1. You should return the optimum price for a rod of length n and price[] as prices of various components.
2. You must build the table val[] from the bottom up and return the last entry.

Code

// A function to get the maximum of two integers

int max(int a, int b) { 

if(a > b)

return a;

else

return b;

}

/* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */

int CutRod(int price[], int n)

{

   int val[n+1];

   val[0] = 0;

   int i, j; 

   // Build the table val[] in bottom up manner and return the last entry

   // from the table

   for (i = 1; i<=n; i++)

   {

       int max_val = INT_MIN;

       for (j = 0; j < i; j++)

         max_val = max(max_val, price[j] + val[i-j-1]);

       val[i] = max_val;

   } 

   return val[n];

}

This brings you to the conclusion of this tutorial. You will now explore your next steps to conquer interviews on programming-based problems.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Steps

Your next stop in mastering Interview Programming problems should be greedy Programming Problems. A greedy algorithm is a straightforward, intuitive approach employed in the optimization of systems of equations. The algorithm makes the best choice possible at each step along the way as it strives to find the overall best solution to the entire problem in question. 

If you're looking for a deeper grasp of software development that will help you carve out a successful career in the sector, you've come to the right place. If this is the case, try Simplilearn's Postgraduate Program in Full Stack Web Development, which is offered in cooperation with Caltech CTME, the world's largest university for technological education. This Post-Graduate Program will teach you how to grasp both front-end and back-end Java technologies, beginning with the fundamentals and proceeding to more complex topics in Full Stack Web Development. You'll learn Angular, Spring Boot, Hibernate, JSPs, and MVC in this web development course, which will prepare you to work as a full-stack developer.

If you have any comments or questions about this "Dyanamic Programming Problem" tutorial, please leave them in the comments below. Our skilled staff will review them and get back to you as quickly as possible.