Dynamic Programming
Tags: computerscience, algorithms, datastructures, csharp
Published: 2020-05-31 21:20:02

## Resources:

1. [In-depth explanation with examples](https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews/m2G1pAq0OO0)
1. [Wikipedia article](https://en.wikipedia.org/wiki/Dynamic_programming)
1. [0/1 Knapsack problem video](https://www.youtube.com/watch?v=xCbYmUPvc2Q)
1. [Longest Common Subsequence (LCS) problem video](https://www.youtube.com/watch?v=ASoaQq66foQ)
1. [Bottom-up LCS implementation](https://github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/dp/LongestCommonSubsequence.java)
1. [Top-down LCS implementation](https://github.com/bephrem1/backtobackswe/blob/master/Dynamic%20Programming,%20Recursion,%20&%20Backtracking/LongestCommonSubsequence/TopDown.java)
1. [Top-down 0/1 Knapsack implementation](https://github.com/bephrem1/backtobackswe/blob/master/Dynamic%20Programming%2C%20Recursion%2C%20%26%20Backtracking/Knapsack01/TopDownNoMemoization.java)
1. [Bottom-up 0/1 Knapsack implementation](https://github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/dp/Knapsack_01.java)

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.](https://www.interviewcake.com/concept/java/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](https://stackoverflow.com/a/34517541/3574076). 

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

{% gist https://gist.github.com/jbolton209/c5f8b4f105270ea0dbfa4748e69d1570
%}

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