[algorithm][dp][leetcode] Dynamic programming thinking

Reference:
[algorithm][DP] thinking steps
Erik Demaine - Dynamic Programming I: Fibonacci, Shortest Paths

Reading note for:
Nikola Otasevic - Dynamic Programming – 7 Steps to Solve any DP Interview Problem

1. Spot if it's a DP problem
   1. Breaking it down into a collection of simpler subproblems.
   2. Solving each of those subproblems just once,
   3. and storing their solutions.
   
   The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution.
   
   This saves computation time at the expense of a modest expenditure in storage space.
   Whether the problem solution can be expressed as a function of solutions to similar smaller problems.
2. Identify problem variables
   Established that there is some recursive structure between our subproblems.
   
   Need to express the problem in terms of the function parameters and see which of those parameters are changing.
   
   Typically in interviews, you will have one or two changing parameters, but technically this could be any number.
    i.e Question: Compute edit distance between strings
   
   Counting the number of changing parameters is valuable to determine the number of subproblems we have to solve, but it is also important in its own right in helping us strengthen the understanding of the recurrence relation from step 1.
3. Clearly express the recurrence relation
   Don't rush into implementation.
   
   Expressing the recurrence relation as clearly as possible will strengthen your problem understanding and make everything else significantly easier.
   
   Once figuring out that the recurrence relation exists and specify the problems in terms of parameters, this should come as a natural step.
   
   Think: How do problems relate to each other? In other words, let's assume that you have computed the subproblems. How would you compute the main problem?
4. Identify the base cases
   (重要!)
   A base case is a subproblem that doesn't depend on any other subproblem.
   (Like FP's ending point/ C++ variadic template)
   
   In order to find such subproblems,
   1. try a few examples, see how problem simplifies into smaller subproblems,
   2. and at what point it cannot be simplified further.
   
   The reason a problem cannot be simplified further is that one of the parameters would become a value that is not possible given 'constraints' of a problem.
   
   It can be a little challenging to convert assertions that we make about parameters into programmable base cases.
   
   This is because, in addition to listing the assertions if want to make code look concise and not check for unnecessary conditions, we need to also think about which of these conditions are even possible.
5. Decide if you want to implement it iteratively or recursively
   i.e (stack overflow consideration, tail call)
   
   In both approaches, you would have to determine the recurrence relation and the base cases.
   
   trade-offs:
   
   
   
   Stack overflow issues are typically a deal breaker and a reason why would not want to have recursion in a (backend) production system.
   
   However, for the purposes of the interview, as long as mentioning the trade-offs, we should typically be fine with either of the implementations.
   Should feel comfortable implementing both.
6. Add memoization
   Used for storing the results of expensive function calls and returning the cached result when the same inputs occur again.
   
   Why are we adding memoization to our recursion? We encounter the same subproblems which without memoization are computed repeatedly.
   Those repetitions very often lead to exponential time complexities.
   
   In recursive solutions, adding memoization should feel straightforward.
   Remember that memoization is just a cache of the function results. There are times when you want to deviate from this definition in order to squeeze out some minor optimizations, but treating memoization as a function result cache is the most intuitive way to implement it.
   
   i.e
   1. Store function result into your memory before every return statement
   
   2. Look up the memory for the function result before start doing any other computation
7. Determine Time complexity
   Count the number of states
       This will depend on the number of changing parameters in the problem
   
   Think about the work done per each state.
        i.e if everything else but one state has been computed, how much work do we have to do to compute that last state