DP

1. When to use dynamic programming?

   1. If we can break the problem into subproblems such that

      1. the original problem can be solved relatively easily once solutions to the subproblems are available

      2. we solve some subproblems repeatedly

      3. we can cache the solution to subproblems

   2. The question usually asks for maximum or minimum.

2. Top-down or bottom-up

   1. top-down:

      1. The question we should ask is: what if the first element is used, what if it's not used?

      2. Usually we can visualize the solution in a tree from top to bottom.

      3. Recursion is often used.

      4. If it's a dynamic programming problem, we can cache the solutions along the way.

      5. Very similar to backtracking solutions. The difference is in backtracking problems, we have to traverse the whole tree to return all the output. But in dynamic programming, we don't need to return all the path. Usually we are updating something along the way.

   2. bottom-up:

      1. The question we should ask is: if we have the solution to the subproblem A[0:n-2], how can we find solution for adding one more element A[n-1]?

      2. We won't traverse the tree, instead there will be linear search.

      3. Iteration is often used.

      4. One advantage of bottom-up is that when processing some paths will be pruned early.

      5. In a dynamic programming problem, try to come up a bottom-up solution first because bottom-up costs less space.

3. Two typical ways when cache results

   1. cache a constant number of results.

      1. In bottom-up solution, when we add element A[n-1] , the information we need from solution to the subproblem A[0:n-2] is up to constant.

      2. Example: 53_Maximum Subarray

   2. cache in a array of the same length as the input

      1. In bottom-up solution, when we add element A[n-1] , the information we need from solution to the subproblem A[0:n-2] is related with each element.

      2. Example: 300_ Longest Increasing Subsequence