Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45

One Stop Solution to All the Dynamic Programming Problems

Lesson - 46

Understanding the Fundamentals of Binomial Distribution

Lesson - 47

Here’s All You Need to Know About Minimum Spanning Tree in Data Structures

Lesson - 48

Understanding the Difference Between Array and Linked List

Lesson - 49

The Best Article Out There to Understand the B+ Tree in Data Structure

Lesson - 50

A Comprehensive Look at Queue in Data Structure

Lesson - 51

Your One-Stop Solution to Understand Coin Change Problem

Lesson - 52

The Best Way to Understand the Matrix Chain Multiplication Problem

Lesson - 53

Your One-Stop Solution to Learn Floyd-Warshall Algorithm for Using Dynamic Programming

Lesson - 54

The Best Tutorial You'll Ever Need for Queue Implementation Using Linked List

Lesson - 55
One Stop Solution to All the Dynamic Programming Problems

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.

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

Dynamic Programming Problems - Longest Common Subsequence

DP_Problems-LCS-img1

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

DP_Problems-LIS-img1

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.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

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

DP_Problems-minimum-edit-img1

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

DP_Problems-distance-cover-img1

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].

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

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

DP_Problems-subset-sum-img1

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];

}

Free Course: Programming Fundamentals

Learn the Basics of ProgrammingEnroll Now
Free Course: Programming Fundamentals

Dynamic Programming Problems - Shortest Common Supersequence 

DP_Problems-SCS-img1

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

DP_Problems-matrix-chain-multiplication-img1

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.

Full Stack Java Developer Course

In Partnership with HIRIST and HackerEarthEXPLORE COURSE
Full Stack Java Developer Course

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

DP_Problems-coin-change-img1

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

DP_Problems-Word-Break-img1

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;

}

FREE Java Certification Training

Learn A-Z of Java like never beforeEnroll Now
FREE Java Certification Training

Dynamic Programming Problems - Rod Cutting Problem

DP_Problems-cut-rod-img1

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.

About the Author

VaibhavVaibhav
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.