© Sammie Bae 2019
Sammie BaeJavaScript Data Structures and Algorithmshttps://doi.org/10.1007/978-1-4842-3988-9_19

19. Dynamic Programming

Sammie Bae1 
(1)
Hamilton, ON, Canada
 

Dynamic programming involves breaking down problems into their subproblems. By solving for the optimal subproblems and saving those results into memory to access them whenever a repeated problem needs to be solved, the algorithmic complexity decreases significantly. Implementing dynamic programming algorithms requires higher-level thinking about the problem’s patterns. To explain dynamic programming, let’s re-examine the Fibonacci sequence that was discussed in Chapter 8. Then the chapter will cover the rules of dynamic programming and walk you through some examples to make the concepts more concrete.

Motivations for Dynamic Programming

The code for the Fibonacci sequence has already been determined to be the following:
function getNthFibo(n) {
    if (n <= 1) {
        return n;
    } else {
        return getNthFibo(n - 1) + getNthFibo(n - 2);
    }
}
getNthFibo(3);
Recall that the recursive implementation of this algorithm is O(2n). This is an exponential runtime, which is impractical for real-world applications. Upon closer examination, you will notice that much of the same computation is repeated. As shown in Figure 19-1, when getNthFibo for 6 is called, the calculation for 4, 3, 2, and 1 are repeated multiple times. Knowing this, how can you make this algorithm more efficient?
../images/465726_1_En_19_Chapter/465726_1_En_19_Fig1_HTML.jpg
Figure 19-1

Recursion tree for Fibonacci numbers

Using a hash table, once the Fibonacci number has been computed, it can be stored like the following implementation:
1   var cache={};
2   function fiboBest(n){
3       if(n<=1)return n;
4       if(cache[n])return cache[n];
5       return (cache[n]=fiboBest(n-1)+fiboBest(n-2));
6   }
7   fiboBest(10); // 55

This is known as overlapping subproblems. Calculating the Fibonacci sequence for 6 requires calculating the Fibonacci sequence for 4 and 5. Hence, the Fibonacci sequence for 5 overlaps with the fourth Fibonacci sequence calculation. This problem also has an optimal substructure, which refers to the fact that the optimal solution to the problem contains optimal solutions to its subproblems.

With this, let’s now formalize what dynamic programming is.

Rules of Dynamic Programming

Dynamic programming (DP) is the method of storing values that were already calculated and using those values to avoid any recalculations (typically in a recursive algorithm). This method can be applied only to those problems with overlapping subproblems and optimal substructure.

Overlapping Subproblems

Similar to divide and conquer in recursion, DP combines solutions on subproblems. DP is used when solutions for subproblems are needed multiple times. It stores subproblem solutions typically in a hash table, an array, or a matrix, and this is referred to as memoization . DP is useful for solving problems in which there are many repeated subproblems.

An example of this can be seen with the Fibonacci sequence recursive method. It can be observed that some numbers such as 3 will be recalculated many times.

A hash table can be used to store results to avoid any recalculations. Doing this reduces the time complexity from O(2n) to just O(n), which is an immense change. Calculating O(2n) with a realistically large enough n can take literally years to compute.

Optimal Substructure

An optimal substructure is when the optimal solution of a problem can be found by using the optimal solutions of its subproblems.

For example, the shortest path finding algorithms have optimal substructures. Consider finding the shortest path for traveling between cities by car. If the shortest route from Los Angeles to Vancouver passes through San Francisco and then Seattle, then the shortest route from San Francisco to Vancouver must pass through Seattle as well.

Example: Ways to Cover Steps

Given a distance, n, count the total number of ways to cover n number of steps with one, two, and three steps. For example, when n=3, there are four combinations (ways), shown here:
  1. 1.

    1 step, 1 step, 1 step, 1 step

     
  2. 2.

    1 step, 1 step, 2 steps

     
  3. 3.

    1 step, 3 steps

     
  4. 4.

    2 steps, 2 steps

     
Here’s the function for achieving the count:
1   function waysToCoverSteps(step){
2       if (step<0) return 0;
3       if (step==0) return 1;
4
5       return waysToCoverSteps(step-1)+waysToCoverSteps(step-2)+waysToCoverSteps(step-3 );
6   }
7   waysToCoverSteps(12);

Time Complexity: O(3n)

This recursive method has a large time complexity. To optimize the time complexity, simply cache the result and use it instead of recalculating the values.
 1   function waysToCoverStepsDP(step) {
 2       var cache = {};
 3       if (step<0) return 0;
 4       if (step==0) return 1;
 5
 6       // check if exists in cache
 7       if (cache[step]) {
 8           return cache[step];
 9       } else {
10           cache[step] = waysToCoverStepsDP(step-1)+waysToCoverStepsDP(step-2)+waysToCoverStepsDP(step-3);
11           return cache[step];
12       }
13   }
14   waysToCoverStepsDP(12);

Time Complexity: O(n)

This shows the power of dynamic programing. It improves time complexity immensely.

Classical Dynamic Programming Examples

This section will explore and solve some of the classical dynamic programming problems. The first one that will be explored is the knapsack problem.

The Knapsack Problem

The knapsack problem is as follows:

  • Given n weights and the values of items, put these items in a knapsack of a given capacity, w, to get the maximum total value in the knapsack.

Optimal Substructure

For every item in the array, the following can be observed:

  • The item is included in the optimal subset.

  • The item is not included in the optimal set.

The maximum value must be one of the following:
  1. 1.

    (excluding the Nth item): max value obtained with n-1 items

     
  2. 2.

    (including the Nth item): max value obtained with n-1 items minus the Nth item (can only work if the weight of the Nth item is smaller than W)

     

Naive Approach

The naive approach implements the described optimal substructure recursively, as shown here:
 1   function knapsackNaive(index, weights, values, target) {
 2       var result = 0;
 3
 4       if (index <= -1 || target <= 0) {
 5           result = 0
 6       } else if (weights[index] > target) {
 7           result = knapsackNaive(index-1, weights, values, target);
 8       } else {
 9           // Case 1:
10           var current = knapsackNaive(index-1, weights, values, target)
11           // Case 2:
12           var currentPlusOther = values[index] +
13               knapsackNaive(index-1, weights, values, target - weights[index]);
14
15           result = Math.max(current, currentPlusOther);
16       }
17       return result;
18   }
19   var weights = [1,2,4,2,5],
20       values  = [5,3,5,3,2],
21       target = 10;
22   knapsackNaive(4,weights, values, target);

Time Complexity: O(2n)

Figure 19-2 shows the recursion tree for a knapsack capacity of 2 units and 3 items of 1 unit weight. As the figure shows, the function computes the same subproblems repeatedly and has an exponential time complexity. To optimize this, you can have the results based on the item (reference via index) and target (weight: w).
../images/465726_1_En_19_Chapter/465726_1_En_19_Fig2_HTML.jpg
Figure 19-2

Recursion tree for knapsack

DP Approach

As discussed, the following DP implementation stores the result of the knapsack using the current array index and target as a key to a JavaScript object for later retrieval. For recursive calls that have already been calculated, it will use the stored result, and this reduces the time complexity of the algorithm significantly.
 1   function knapsackDP(index, weights, values, target, matrixDP) {
 2       var result = 0;
 3
 4       // DP part
 5       if (matrixDP[index + '-' + target]){
 6           return matrixDP[index + '-' + target];
 7       }
 8
 9       if (index <= -1 || target <= 0) {
10           result = 0
11       } else if (weights[index] > target) {
12           result = knapsackDP(index - 1, weights, values, target, matrixDP);
13       } else {
14           var current = knapsackDP(index-1, weights, values, target),
15               currentPlusOther = values[index] + knapsackDP(index-1, weights, values, target - weights[index]);
16           result = Math.max(current, currentPlusOther);
17       }
18       matrixDP[index + '-' + target] = result
19       return result;
20   }
21   knapsackDP(4, weights, values, target, {});

Time Complexity: O(n*w )

Here, n is the number of items, and w is the capacity of the knapsack.

Space Complexity: O(n*w )

This algorithm requires an n times wcombination to store the cached results inside matrixDP.

The next DP question that will be studied is another classic.

Longest Common Subsequence

Given two sequences, find the length of the longest subsequence where a subsequence is defined as a sequence that appears in relative order without necessarily being contiguous. For example, sam, sie, aie, and so forth, are subsequences of sammie. A string has 2n possible subsequences where n is the length of the string.

As a real-world example, let’s consider a generalized computer science problem that appears in main domains such as bioinformatics (DNA sequencing). This algorithm is also how the diff functionality (file comparison to output difference between files) is implemented in version control and operating systems.

Naive Approach

Letting str1 be the first string of length m, str2 be the second string of length n, and LCS be the function, the naive approach can first consider the following pseudocode:
1.  if last characters of both sequences match (i.e. str1[m-1] == str2[n-1]):
2.     result = 1 + LCS(X[0:m-2], Y[0:n-2])
3.  if last characters of both sequences DO NOT match (i.e. str1[m-1] != str2[n-1]):
4.     result = Math.max(LCS(X[0:m-1], Y[0:n-1]),LCS(X[0:m-2], Y[0:n-2]))
With this recursive structure in mind, the following can be implemented:
 1   function LCSNaive(str1, str2, str1Length, str2Length) {
 2       if (str1Length == 0 || str2Length == 0) {
 3           return 0;
 4       }
 5
 6       if (str1[str1Length-1] == str2[str2Length-1]) {
 7           return 1 + LCSNaive(str1, str2,
 8                               str1Length - 1,
 9                               str2Length - 1);
10       } else {
11           return Math.max(
12               LCSNaive(str1, str2, str1Length, str2Length-1),
13               LCSNaive(str1, str2, str1Length-1, str2Length)
14           );
15       }
16   }
17
18   function LCSNaiveWrapper(str1, str2) {
19       return LCSNaive(str1, str2, str1.length, str2.length);
20   }
21   LCSNaiveWrapper('AGGTAB', 'GXTXAYB'); // 4

Time Complexity: O(2n)

Figure 19-3 shows the recursion tree for SAM and BAE (visually cut off at a height of 3). As you can see, ('SA', 'BAE') is repeated.
../images/465726_1_En_19_Chapter/465726_1_En_19_Fig3_HTML.jpg
Figure 19-3

Recursion tree for longest common string length

DP Approach

The recursive structure described can be translated into a table/cache where the rows each represent a character in str1 and the columns each represent a character in str2. Each item in a matrix at a row, i, and a column, j, represents LCS(str1[0:i], str2[0:j]).
 1   function longestCommonSequenceLength(str1, str2) {
 2       var matrix = Array(str1.length + 1).fill(Array(str2.length + 1).fill(0)),
 3           rowLength = str1.length + 1,
 4           colLength = str2.length + 1,
 5           max = 0;
 6
 7       for (var row = 1; row < rowLength; row++) {
 8           for (var col = 1; col < colLength; col++) {
 9               var str1Char = str1.charAt(row - 1),
10                   str2Char = str2.charAt(col - 1);
11
12               if (str1Char == str2Char) {
13                   matrix[row][col] = matrix[row - 1][col - 1] + 1;
14                   max = Math.max(matrix[row][col], max);
15               }
16           }
17       }
18       return max;
19   }
20   longestCommonSequenceLength('abcd', 'bc');

Time Complexity: O(m * n)

Space Complexity: O(m * n)

Here, m is the length of str1, and n is the length of str2.

Coin Change

Given a value/money n and an unlimited supply of each coin of different values, S = {S1, S2, .. Sm}, of size M, how many ways can the change be made without considering the order of the coins?

Given N=4, M=3, and S = {1,2,3}, the answer is 4.
1.   1,1,1,1,
2.   1,1,2
3.   2,2
4.   1,3

Optimal Substructure

You can observe the following about the number of coin changes:
1)   Solutions without Mth coin
2)   Solutions with (at least) one Mth coin
Given that coinChange(S, M, N) is a function to count the number of coin changes, mathematically it can be rewritten as follows by using the two observations from earlier:
coinChange(S, M, N) = coinChange(S, M-1, N) + coinChange(S, M, N-Sm)

Naive Approach

The naive approach can implement the described algorithm using recursion, as shown here:
 1   // Returns the count of ways we can sum coinArr which have
 2   // index like: [0,...,numCoins]
 3   function countCoinWays(coinArr, numCoins, coinValue){
 4       if (coinValue == 0) {
 5           // if the value reached zero, then only solution is
 6           // to not include any coin
 7           return 1;
 8       }
 9       if (coinValue < 0 || (numCoins<=0 && coinValue >= 1)) {
10           // value is less than 0 means no solution
11           // no coins left but coinValue left also means no solution
12           return 0;
13       }
14       //
15       return countCoinWays(coinArr,numCoins-1, coinValue) +
16           countCoinWays(coinArr,numCoins, coinValue-coinArr[numCoins-1]);
17   }
18   function countCoinWaysWrapper(coinArr, coinValue) {
19       return countCoinWays(coinArr, coinArr.length, coinValue);
20   }
21   countCoinWaysWrapper([1,2,3],4);

Time Complexity: O(nm)

Space Complexity: O(n)

Here, m is the number of available types of coins, and n is the desired currency to convert into change.

Overlapping Subproblems

You can see from the recursion tree in Figure 19-4 that there are lots of overlapping subproblems.
../images/465726_1_En_19_Chapter/465726_1_En_19_Fig4_HTML.jpg
Figure 19-4

Recursion tree for longest coin change

To account solve for this, a table (matrix) can be used to store already computed results.

DP Approach

The matrix for the DP approach has the coinValue number of rows and the numCoins number of columns. Any matrix at i and j represent the number of ways given a coinValue of i and a numCoins of j.
 1   function countCoinWaysDP(coinArr, numCoins, coinValue) {
 2       // creating the matrix
 3       var dpMatrix = [];
 4
 5       for (var i=0; i <= coinValue; i++) {
 6           dpMatrix[i] = [];
 7           for(var j=0; j< numCoins; j++) {
 8               dpMatrix[i][j] = undefined;
 9           }
10       }
11
12       for (var i=0; i < numCoins; i++) {
13           dpMatrix[0][i] = 1;
14       }
15
16       for (var i=1; i < coinValue + 1; i++) {
17           for (var j=0; j < numCoins; j++) {
18               var temp1 = 0,
19                   temp2 = 0;
20
21               if (i - coinArr[j] >= 0) {
22                   // solutions including coinArr[j]
23                   temp1 = dpMatrix[i - coinArr[j]][j];
24               }
25
26               if (j >= 1) {
27                   // solutions excluding coinArr[j]
28                   temp2 = dpMatrix[i][j-1];
29               }
30
31               dpMatrix[i][j] = temp1 + temp2;
32           }
33       }
34       return dpMatrix[coinValue][numCoins-1];
35   }
36
37   function countCoinWaysDPWrapper(coinArr, coinValue) {
38       return countCoinWaysDP(coinArr, coinArr.length, coinValue);
39   }
40   countCoinWaysDPWrapper([1,2,3],4);

Time Complexity: O(m * n)

Space Complexity: O(m * n)

Here, m is the number of available types of coins, and n is the desired currency to convert into change.

Edit (Levenshtein) Distance

The edit distance problem considers the following :

  • Given a string (str1) of length m and another string (str2) of length n, what is the minimum number of edits to convert str1 into str2?

The valid operations are the following:
  1. 1.

    Insert

     
  2. 2.

    Remove

     
  3. 3.

    Replace

     

Optimal Substructure

If each character is processed one by one from each str1 and str2, the following is possible:
1.   the characters are the same:
      do nothing
2.   the characters are different:
      consider the cases recursively:
          Insert:     for m   and n-1
          Remove:     for m-1 and n
          Replace:    for m-1 and n-1

Naive Approach

The naive approach can implement the described substructure recursively, as shown here:
 1   function editDistanceRecursive(str1, str2, length1, length2) {
 2       // str1 is empty. only option is insert all of str2
 3       if (length1 == 0) {
 4           return length2;
 5       }
 6       // str2 is empty. only option is insert all of str1
 7       if (length2 == 0) {
 8           return length1;
 9       }
10
11       // last chars are same,
12       // ignore last chars and count remaining
13       if (str1[length1-1] == str2[length2-1]) {
14           return editDistanceRecursive(str1, str2,
15                                        length1-1, length2-1);
16       }
17
18       // last char is not the same
19       // there are three operations: insert, remove, replace
20       return 1 + Math.min (
21           // insert
22           editDistanceRecursive(str1, str2, length1, length2-1),
23           // remove
24           editDistanceRecursive(str1, str2, length1-1, length2),
25           // replace
26           editDistanceRecursive(str1, str2, length1-1, length2-1)
27       );
28   }
29
30   function editDistanceRecursiveWrapper(str1, str2) {
31       return editDistanceRecursive(str1, str2, str1.length, str2.length);
32   }
33
34   editDistanceRecursiveWrapper('sammie','bae');

Time Complexity: O(3m)

The time complexity of the naive solution is exponential, and the worst case is when no characters in the two strings match. This makes sense because each call has three calls (insert, remove, replace).

Again, you can see that the same problems are solved over and over again (see Figure 19-5). This can be optimized by constructing a matrix that stores the already-computed results of subproblems.
../images/465726_1_En_19_Chapter/465726_1_En_19_Fig5_HTML.jpg
Figure 19-5

Recursion tree for edit distance

DP Approach

The dynamic programming approach will construct a matrix with the dimensions str1 and str2. The base case is when i or j is equal to 0. In other cases, it is 1 + min(insert, remove, replace) just like the recursive approach.
 1   function editDistanceDP(str1, str2, length1, length2) {
 2       // creating the matrix
 3       var dpMatrix = [];
 4       for(var i=0; i<length1+1; i++) {
 5           dpMatrix[i] = [];
 6           for(var j=0; j<length2+1; j++) {
 7               dpMatrix[i][j] = undefined;
 8           }
 9       }
10
11       for (var i=0; i < length1 + 1; i++) {
12           for (var j=0; j < length2 + 1; j++) {
13               // if first str1 is empty,
14               // have to insert all the chars of str2
15               if (i == 0) {
16                   dpMatrix[i][j] = j;
17               } else if (j == 0) {
18                   dpMatrix[i][j] = i;
19               } else if (str1[i-1] == str2[j-1]) {
20                   // if the same, no additional cost
21                   dpMatrix[i][j] = dpMatrix[i-1][j-1];
22               } else {
23                   var insertCost = dpMatrix[i][j-1],
24                       removeCost = dpMatrix[i-1][j],
25                       replaceCost= dpMatrix[i-1][j-1];
26
27                   dpMatrix[i][j] = 1 + Math.min(insertCost,removeCost,replaceCost);
28               }
29           }
30       }
31       return dpMatrix[length1][length2];
32   }
33
34   function editDistanceDPWrapper(str1, str2) {
35       return editDistanceDP(str1, str2, str1.length, str2.length);
36   }
37
38   editDistanceDPWrapper('sammie','bae');

Time Complexity: O(m * n)

Space Complexity: O(m * n)

Here, m is the length of str1, and n is the length of str2.

Summary

Dynamic programming can be utilized to optimize an algorithm if the following conditions are satisfied:

  • Optimal substructure: The optimal solution to the problem contains optimal solutions to its subproblems.

  • Overlapping subproblems: The solutions for subproblems are needed multiple times.

To store the already computed solutions to a subproblem, a matrix or a hash table is typically used; this is because both provide O(1) lookup time. Doing this, the time complexity can be improved from exponential (e.g., O(2n )) to polynomial time (e.g., O(n2)).