JB

Posted on

# Dynamic Programming

## Resources:

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)`).

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!