loading...

Dynamic Programming

jjb profile image JB ・7 min read

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

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

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!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Posted on May 31 by:

Discussion

markdown guide