CS Level Up Series (30 Part Series)
Resources:
 Indepth explanation with examples
 Wikipedia article
 0/1 Knapsack problem video
 Longest Common Subsequence (LCS) problem video
 Bottomup LCS implementation
 Topdown LCS implementation
 Topdown 0/1 Knapsack implementation
 Bottomup 0/1 Knapsack implementation
Takeaways:
 Dynamic programming is a process by which a larger problem is reduced to subproblems.
 These subproblems are easier to reason about, easier to solve individually, and are typically decision problems.
 By solving these subproblems, 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 subproblems.
 Dynamic programming solutions are usually either topdown or bottomup.
 Topdown means we start from our input(s) and work downwards to our basecase using recursion (remember recursive functions have a basecase that determines when the recursion should end, similar to an exit condition in a while loop).
 Bottomup means we start from the basecase and work upwards.
 Bottomup is recursion free and thus will avoid building up a call stack of
O(n)
size. This means bottomup approaches can be more memory efficient than their topdown counterparts.
 Bottomup is recursion free and thus will avoid building up a call stack of
 Topdown solutions use recursion and memoization to solve the larger problem, whereas bottomup solutions will use a nested forloop 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 subproblem solution table, or matrix, is a matrix with each coordinate (
x,y
) containing the answer to a subproblem (x,y
axis are representations of the problem inputs).  For example,
x
might represent a weight input, andy
might represent acost
input. Given a weight of1
and a cost of$3
we can find out in our matrix what the optimal solution is for those inputs by going to thex,y
coordinates1,3
.  Topdown dynamic programming solutions memoize the solutions to subproblems to avoid duplicated work.
 Bottomup 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 subproblem 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 topdown and bottomup 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 beingO(n)
 The algorithm would be something like:
 Define a recursive function (e.g
solveKnapsack(int[] values, int[] weights, int weightLimit, int index)
)  Define a basecase 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 ofi
isvalues[i]
, weight ofi
isweight[i]
): Compute a value
v1
which includes itemi
if it's weight is lower than our weight limit, deducti
's weight from our limit & then recursively process the remaining items.  Otherwise, if
i
has a weight greater than our limit, compute a valuev2
which exludes itemi
and then recursively process the remaining items.
 Compute a value
 At the end of our recursive function, return the maximum between
v1
andv2
.
 Define a recursive function (e.g
 This approach is exponential
 If our naive approach is written recursively similar to described, then we can see that this approach is topdown  it is working from our inputs downwards to a basecase.
 Each call to
solveKnapsack
in our naive solution is solving a subproblem: do we include or exlude itemi
? And whatever the answer, what is the value (v1
orv2
) 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 subproblems. This will help to avoid duplicated work (assuming we also add a check that will return the memoized value/subproblem solution, if it has already been solved)
 A bottomup 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 topdown and bottomup solutions are
O(nm)
wheren
is the number of items andm
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
andinputB
, 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.
 Given two strings

So what exactly is a subsequence?
 A subsequence of a string
A
is a new stringB
that has some of the characters fromA
deleted, without changing the relative order of the remaining characters. This is unlike a substring, which is simply a subsection of another string.
 For example: given
A = "abcdefg"
a subsequenceB
could be"acdeg"
or"ag"
or"abd"
. Notice howB
's characters all exist inA
? 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 ofA
.  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 subsequnceC
of the two isC = "el"
.
 A subsequence of a string

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]
andinputB[0..m]
. The longest subsequence that exists in both inputs will be returned. This approach is
O(n * 2^m)
 This approach is
 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 bothinputA
&inputB
end with the same character then we remove the trailing character from each and recursively callsolveLCS(inputA[0..n1], inputB[0..m1])
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
andinputB
((inputA[0..n1], inputB[0..m])
&(inputA[0..n], inputB[0..m1])
), after computing the LCS of both we return the larger of the two values.
 We do this for both
 The basecase for our naive recursive algorithm checks if
inputA
orinputB
are empty strings (as we will be removing characters from each during the recursion).
 For each recursive call to
 The naive approach, again, is brute force and checks every possible subsequence in
Like 0/1 Knapsack, to transform the naive recursive solution into a dynamic topdown 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 subproblem's solution. We effectively cache each decision made in the recursive routine.
Again, like with 0/1 Knapsack, a bottomup solution will not use recursion and instead, upfront, build the solution matrix using a nested forloop. 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 topdown and bottomup LCS solutions are
O(nm)
wheren
is the number of characters ininputA
andm
is the number of characters ininputB
. The topdown solution, due to recursion, is technicallyO(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)
wherek
is nonnegative. 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 topdown & bottomup solutions to LCS & 0/1 Knapsack problems, with test cases:
As always, if you found any errors in this post please let me know!
CS Level Up Series (30 Part Series)
Discussion