Dynamic Programming

• Most of DP problems can be divided into two types: optimization problems and combinatoric problems.
  • The optimization problems require you to choose some feasible solution so that the value of goal function is minimized (or maximized). You are often trying to either minimize or maximize a decision. You are given two (or more) options at any given point and you have to decide which is more optimal for the problem you’re trying to solve. These decisions, however, are based on previous choices you made.
    • The optimal substructure vares n how many subproblems are used n an optimal solution to the original problem and how many choices we have in detemining which subproblems to use.

      Optimal Parenthisizaton: 2 subproblems used, n choices at most
      Activity Selection Naive: 2 subproblems, n choices at most.
      Acvitity Selection Greedy Observation: 1 subproblem, 1 choice
      Assembly Line Scheduling: 1 subproblems used 2 choices

    • The cost of the problem is usually the subproblem cost plus a cost that is directly attributable to the choice itself.
    • In case of minimization problem the neutral value is positive infinity: since it is greater than any number, all the recurrent formulas would prefer a case with finite value to such a neutral element. In other words, the state with neutral value result can be thought of as an impossible state. Note that for maximization problem negative infinity is a neutral element.
  • Combinatoric problems request the number of ways to do something or the probability of some event. There is also a neutral value for combinatoric problem. Since combinatoric problem uses summation, the neutral element is zero. The DP results in combinatoric case usually represents number of ways to do smth, so if the result is zero than there is no way to do it. The neutral result value means that the case is impossible. It may be useful to fill DP results array with zero values, though it is usually done automatically. In case of combinatorics it is important that each possible way is counted and that no way is counted more than once. The second condition is sometimes difficult to satisfy. Sometimes it help to keep the base case of counting as 1 (e.g. In coin combinations, this numbers the number of ways to make amount 0 using all the coins is 1, while in minCoins, the minimum coins needed to make zero would be 0.).
• CLRS recipe:
  • You show that the solution involves making a choice.

    Assmebly line: Choosing a preddig assembly line staton
    Matrix Chan Mult: Choosing an index at which to split

  • Assume you made the choice. Given this choice, what smaller problems ensue and how do you characterize them?

• It is often useful to fill the DP results array with neutral values before calculating anything. The neutral value is a result which does not affect the problem answer for sure

• Then consider an iterative bottom up approach (DP), or a recursive memoized approach (memoization). Make recursion tree to illustrate the difference. Memoization is an optimization of a top-down, depth-first computation for an answer. DP is an optimization of a bottom-up, breadth-first computation for an answer. (Question: What about bottom-up, depth-first or top-down, breadth first? Where do they fit into the space of techniques for avoiding recomputation by trading off space for time?) In top-down approach (as we do in reedy), we make a choice (in greedy this s the greedy choice), and then solve subproblems. In bottom up, we solve subproblems first and then make the choce.

• First write the computation and observe whether it fits the DAG pattern; if it does, use memoization. Only if the space proves to be a problem and a specialized memo strategy won’t help—or, even less likely, the cost of “has it already been computed” is also a problem—should you think about converting to DP. And when you do, do so in a methodical way, retaining structural similarity to the original.

• It can be easier to think using a forward strategy (i.e. I know the value at a given cell in the DP table and I want to see what other cells depend on it). This approach makes it easier to separately consider the cases that make up the recursion. Otherwise, you might be tempted to prematurely mix all the cases together in some gigantic formula (and there’s a good chance that you’ll get lost before you find the correct formula). Next, think of how to initialize your solution and how to obtain the desired result from the DP table.
  • We now have an oriented graph of dependencies (value of cache[be][en] depends on cache[be][i]). This graph is directed and acyclic. Terminal vertices (with no outgoing edges) represent the base case entries, which we already calculated. Therefore it is sufficient to topologically sort the graph and process the vertices in the order from the terminal vertices.
  • If a problem can be solved by dynamic programming, there is a directed acyclic graph of states and dependencies between them. There is a state that interests us. There are also base states for which we know the answer right away. We can traverse that graph from the vertex that interests us to all its dependencies, from them to all their dependencies in turn, etc., stopping to branch further at the base states. This can be done via recursion.
    • A directed acyclic graph can be viewed as a partial order on vertices. We can topologically sort that graph and visit the vertices in sorted order. Additionally, you can find some simple total orderwhich is consistent with your partial order.
    • Bottom-up DP is equivalent to getting the directed acyclic graph formed by the DFS, running a topological sort on it, and computing the recurrence on each node in order without actually recursing. The key observation is that the topological sort ensures that each time you solve the recurrence for a state, the solutions of the ‘children’ states is already computed due to the topological ordering. In practice you rarely run an explicit topological sort and instead exploit some inherent topological ordering in the problem.
    • Also note that we can often observe some structure on states. For example, the states can be often expressed as integers or tuples of integers. So, instead of using generic caching techniques (e.g., associative arrays to store state->value pairs), we may be able to preallocate a regular array which is easier and faster to use. https://stackoverflow.com/questions/22918242/is-dynamic-programming-backtracking-with-cache
    • “Forward DP”: When we visit a state u, we look at all states v that depend on it and account for u in each of these states for u = 1, 2, 3, …, n - 1: add F[u] to F[u + 1] add F[u] to F[u + 2] the imperative code cannot be readily expressed by a mathematical formula.
    • The paradigm of forward DP style is to iterate through all the DP states and from each state perform some transitions leading forward to other states. Each transition modifies the currently stored result for some unprocessed states. When the state is considered, its result is already determined completely. The forward formulation does not use recurrent equations, so it is more complex to prove the correctness of solution strictly mathematically. The recurrent relations used in forward-style DP are obtained by considering one partial solution for the state and trying to continue it to larger states. To perform forward-style DP it is necessary to fill the DP results with neutral values before starting the calculation. One interpretation of the value stores in the state is the “best solution to the subproblem till now”
    • we have to rewrite the computation to express the delta from each computational tree/DAG node to its parents. We need a means for addressing/naming those parents (which we did not need in the top-down case, since this was implicit in the recursive call stack). This leads to inventions like DP tables, but people often fail to understand why they exist: it’s primarily as a naming mechanism (and while we’re at it, why not make it efficient to find a named element, ergo arrays and matrices). In contrast, in DP it’s easier to save space because you can just look at the delta function to see how far “back” it reaches; beyond there lies garbage, and you can come up with a cleverer representation that stores just the relevant part (the “fringe”). Once you understand this, you realize that the classic textbook linear, iterative computation of the fibonacci is just an extreme example of DP, where the entire “table” has been reduced to two iteration variables.
  • From practical point of view, you don’t want to explicitly create the graph of dependencies and sort it. Instead you want to find a simple invariant between the dependencies and iterate states based on that invariant. For this problem the invariant is: if cache[a][b] depends on cache[x][y], then (b-a) > (y-x). In other words, it is sufficient to iterate on the values be and en in such a way, that the distance between be and en will increase. In this way we will never try compute the value of cache[a][b] before we computed cache[x][y]. (Another example, incline change: the recursion satisfies the weak ordering isplaystyle R(n,m)<R(x,y)\iff n\leq x,m\leq y,(n,m)\neq (x,y)}.https://www.quora.com/How-do-I-figure-out-how-to-iterate-over-the-parameters-and-write-bottom-up-solutions-to-dynamic-programming-related-problems
• How to reconstruct the optimal solution in optimisation DP problems?
  • Starting from end state, reconstruct using relation between states to figure out previous state
  • Caching the previous state (e.g. previous amount made with min coins) and any other data (e.g. coin value added) at the time the decision is made to select one state. This is better because:
    • No code repetition
    • Faster. Co computation repetition
• Dynamic Programming vs Memoization

The DP solution iterates through the states in some particular order set by coder, while memoization iterates through them in order of depth-first search

Running time

The running time depends on the product of two factors: the number of subproblems overall and how many choices we look at for each subproblem.

Assembly Line Scheduling: O(n) subproblems, and 2 choices => O(n) Matrix Chain Multiplication: O(n^2) subproblems, O(n) choices => O(n^3)

Why use Bottom Up DP?

Pro:

• Possible to make memory optimisations by freeing up space. (Analyse what subproblem solutions need to be saved at any point). can more easily save space by disposing of unnecessary sub-computation results
• No Cache Checking Overhead. Has no need to check whether a computation has been done before doing it—the computation is rewritten to ensure this isn’t necessary Cons:
• Difficult to understand and prone to bugs: forces change in desription of the algorithm, which may introduce errors and certainly introduces some maintenance overhead
• Does unnecessary sub-computations (cannot avoid them, and may waste the space associated with storing those results).
• Has a space complexity that depends on picking a smart data storage strategy

Why use memoization?

Pros

• leaves computational description unchanged (black-box)
• avoids unnecessary sub-computations (i.e., saves time, and some space with it). Only necessary subproblems are solved.

Cons

• Possible Stack Overflow due to recursion
• hard to save space absent a strategy for what sub-computations to dispose of. Extra space needs to be maintained, since we do not know a priori which subproblems do not need to be solved.
• Cache checking overhead. must alway check whether a sub-computation has already been done before doing it (which incurs a small cost)
• has a time complexity that depends on picking a smart computation name lookup strategy

Running time:

Consider drawing the subproblem graph for bottom up solution. Count the number of subproblems using parameters space. Find out running time of each. See if any parameters have stricter bounds. Use substitution (guessing) method to solve recurrence.

References:

• 7 Steps to Solve any DP problem

---

28 May 2018