Dynamic Programming

Resources:

1. In-depth explanation with examples
2. Wikipedia article
3. 0/1 Knapsack problem video
4. Longest Common Subsequence (LCS) problem video
5. Bottom-up LCS implementation
6. Top-down LCS implementation
7. Top-down 0/1 Knapsack implementation
8. Bottom-up 0/1 Knapsack implementation

Takeaways:

• Dynamic programming is a process by which a larger problem is reduced to sub-problems.
• These sub-problems are easier to reason about, easier to solve individually, and are typically decision problems.
• By solving these sub-problems, dynamic programming enables us to build up an answer to the larger, more complex, problem.
• If a problem can be solved optimally in this way then the problem is considered to have an optimal substructure.
  • Optimal substructure just means that a problem has an optimal solution that has been constructed from optimal solutions of it's sub-problems.
• Dynamic programming solutions are usually either top-down or bottom-up.
  • Top-down means we start from our input(s) and work downwards to our base-case using recursion (remember recursive functions have a base-case that determines when the recursion should end, similar to an exit condition in a while loop).
  • Bottom-up means we start from the base-case and work upwards.
    • Bottom-up is recursion free and thus will avoid building up a call stack of O(n) size. This means bottom-up approaches can be more memory efficient than their top-down counterparts.
• Top-down solutions use recursion and memoization to solve the larger problem, whereas bottom-up solutions will use a nested for-loop to build a solution matrix/table before contructing the answer from the matrix.
  • Memoization is sort of like caching. We remember the results of a computation so we don't have to recompute the same thing over and over. We instead check the "cache" and see if we have already done the work previously. Here's a good article on memoization.
  • A sub-problem solution table, or matrix, is a matrix with each coordinate (x,y) containing the answer to a sub-problem (x,y axis are representations of the problem inputs).
  • For example, x might represent a weight input, and y might represent a cost input. Given a weight of 1 and a cost of $3 we can find out in our matrix what the optimal solution is for those inputs by going to the x,y coordinates 1,3.
  • Top-down dynamic programming solutions memoize the solutions to sub-problems to avoid duplicated work.
  • Bottom-up solutions merely keep a solution matrix/table in memory, but only use it for constructing the solution - meaning technically there is no memoization, as the same sub-problem does not get solved more than once.
• A famous dynamic programming problem is the 0/1 Knapsack problem
• The 0/1 Knapsack problem statement is:
  • Given a knapsack & a set of items (each item has a weight and value) determine the items to put in your knapsack. The total weight of the knapsack must be less than or equal to a given limit, and the total value should be as large as possible.
  • The items cannot be split/divided. Which is where the 0/1 comes from - we either take an item or leave it.
• The following is an overview of solutions to 0/1 Knapsack (at the conclusion of this post you will find actual code for both top-down and bottom-up solutions):
• The naive, brute force, solution to 0/1 Knapsack is to try all possible combinations of items, keeping track of which subset yields the greatest value whilst being under the weight limit.
  • This approach is exponential O(2^n), with space being O(n)
  • The algorithm would be something like:
    • Define a recursive function (e.g solveKnapsack(int[] values, int[] weights, int weightLimit, int index))
    • Define a base-case at the start of our function that will ensure our index and weight limit are not out of bounds.
    • For each item i (i.e value of i is values[i], weight of i is weight[i]):
      • Compute a value v1 which includes item i if it's weight is lower than our weight limit, deduct i's weight from our limit & then recursively process the remaining items.
      • Otherwise, if i has a weight greater than our limit, compute a value v2 which exludes item i and then recursively process the remaining items.
    • At the end of our recursive function, return the maximum between v1 and v2.
• If our naive approach is written recursively similar to described, then we can see that this approach is top-down - it is working from our inputs downwards to a base-case.
• Each call to solveKnapsack in our naive solution is solving a sub-problem: do we include or exlude item i? And whatever the answer, what is the value (v1 or v2) of that decision?
• We can add an extra parameter (representing a table or matrix) to our function that could be used to memoize the results of these sub-problems. This will help to avoid duplicated work (assuming we also add a check that will return the memoized value/sub-problem solution, if it has already been solved)
• A bottom-up approach merely removes recursion from our previous solution and builds up the matrix at the start of the function. We can then use the matrix to determine things like: what is the maximum value? what items were selected? (via backtracking).

• Time & space complexities for the top-down and bottom-up solutions are O(nm) where n is the number of items and m is the weight limit.

• Another famous problem that can be solved with dynamic programming is Longest Common Subsequence (LCS).

• LCS problem statement is:

  • Given two strings inputA and inputB, return the length of their longest common subsequence.
  • Other variations might also ask you to return the LCS string itself. In my implementations I return the length, but also print the LCS before returning.

• So what exactly is a subsequence?

  • A subsequence of a string A is a new string B that has some of the characters from A deleted, without changing the relative order of the remaining characters.
    • This is unlike a substring, which is simply a sub-section of another string.
    • For example: given A = "abcdefg" a subsequence B could be "acdeg" or "ag" or "abd". Notice how B's characters all exist in A? And how each character's relative position is unchanged?
    • "acb" & "dac" would represent a change in the relative order and so are examples of invalid subsequences of A.
    • Further, we can say that if two strings share a subsequence it is a common subsequence. An example of a common subsequence: Given two strings A & B(A = "hello", B = "below") a common subsequnce C of the two is C = "el".

• The solutions to LCS are strikingly similar to the ones for 0/1 Knapsack:

  • The naive approach, again, is brute force and checks every possible subsequence in inputA[0..n] and inputB[0..m]. The longest subsequence that exists in both inputs will be returned.
    • This approach is O(n * 2^m)
  • But what decisions does our naive approach make? How is it finding the subsequences?
    • For each recursive call to solveLCS(string inputA, string inputB), if both inputA & inputB end with the same character then we remove the trailing character from each and recursively call solveLCS(inputA[0..n-1], inputB[0..m-1]) and return the result.
      • Why? Because if they end with the same character, that means we have found a subsequence - we remove that character and process the rest of each string to determine how long the longest subsequence is.
    • If our inputs do not have the same last character, then we have yet to identify a subsequence so we must remove a trailing character from one of the inputs and recursively call solveLCS(), returning the result.
      • We do this for both inputA and inputB ((inputA[0..n-1], inputB[0..m]) & (inputA[0..n], inputB[0..m-1])), after computing the LCS of both we return the larger of the two values.
    • The base-case for our naive recursive algorithm checks if inputA or inputB are empty strings (as we will be removing characters from each during the recursion).

• Like 0/1 Knapsack, to transform the naive recursive solution into a dynamic top-down solution all we need to do is add an additional data structure as a parameter. This parameter will represent our table/matrix and will be used to memoize each sub-problem's solution. We effectively cache each decision made in the recursive routine.

• Again, like with 0/1 Knapsack, a bottom-up solution will not use recursion and instead, upfront, build the solution matrix using a nested for-loop. From the resulting matrix we can deduce solutions to: what is the longest common subsequence? What characters are in that subsequence?

• Time & space complexities for the top-down and bottom-up LCS solutions are O(nm) where n is the number of characters in inputA and m is the number of characters in inputB. The top-down solution, due to recursion, is technically O(nm + n) - but asymptotically we don't factor in the extra cost (because it is constant).

Lastly, you will notice that both 0/1 Knapsack and LCS problems are solvable in exponential time when approached naively. Dynamic programming not only gives us a blueprint for solving both, but enables us to reduce the running time for both these problems to polynomial running time (specifically O(nm)).

• Polynomial running time is simply a category of running times. Formally, it is any running time that is O(n^k) where k is non-negative. Polynomial running time is much better than exponential running time. Here is a good comparison of various time complexities and their rates of growth.

Below are top-down & bottom-up solutions to LCS & 0/1 Knapsack problems, with test cases:

As always, if you found any errors in this post please let me know!