To solve a DP problem, usually there are four steps:

1. Identify a DP Problem

Typically, all the problems that require to maximize or minimize certain quantity or counting problems that say to count the arrangements under certain condition or certain probability problems can be solved by using Dynamic Programming.

Like recursion, the key point is to figure out the sub problem and cache the result during recursion.Typically, two prerequisites can help us identify an dp problem:

1. overlapping sub-problems.

2. the optimal solution is a combination of optimal solution of sub-problems.

2. Decide a state expression with least parameters

DP problems are all about state and their transition. This is the most basic step which must be done very carefully because the state transition depends on the choice of state definition you make.

State A state can be defined as the set of parameters that can uniquely identify a certain position or standing in the given problem. This set of parameters should be as small as possible to reduce state space. For example, for an array problem, it can be the optimal value of items from range 0 to index.

3. Formulate state relationship

This part is usually the hardest part. We try to build the connect between a smaller sub problem and the larger sub problem. Typically, it is in the form of state(i) = func(state(i-1) + nums[i]).

4. Do tabulation (or add memoization)

Once we set up the above recursion problem, we can relatively easy to finally solve the problem from either of the following two approaches:

1) bottom up(Tabulation)

Notice that in tabulation dp[* i], dp[i-1] can always been set to one variable, so that the memory is reduced from O(n) to O(1).

2) top down(Memorization)

1. One dimension array problems: always think about tabulation first. The sub problem is typically solved by setting dp[i] = the answer ends/starts at index i, dp[i] = functionn(dp[i-1], ..).

House Robber dp[i] = max(dp[i-1], dp[i-2] + nums[i]);

Min Cost Climbing Stairs dp[i] = cost[i] + min(dp[i-1], dp[i-2])

Maximum Subarray (it equals to dp[i] = A[i] + (dp[i-1] > 0? dp[i-1]: 0), where dp[i] represents the max subarray ending in A[i])

Best Time to Buy Sell Stock (it equals to dp[i] = max(dp[i-1], prices[i] - minPrice), where dp[i] contains the max profit up to date i)

Best Time to Buy Sell Stock with Fee (The key here is to separate into two arrays, keeping track of max profit holding at time t and not holding time at t. Again, since only the previous value is used, the memory of two array can be reduced to two variables.)

Climbing Stairs (Basically, it equals to Fibonacci, where dp[i] = dp[i-1] + dp[i-2])

Arithmetic Series (if(difference with the previous == diff between prev and prev prev) dp[i] = dp[i-1] + 1)

Longest Increasing Sequence (This problem has a O(NlogN) solution using binary search compared with the O(N^2) using DP. In binary search method, the idea is similar to use a stack to maintain a sorted array for elements visited so far. When we encounter an element bigger than the end of the stack, we push it back to the stack. Otherwise, we put it in the right position by override the old one. The way to find the right position is to use a binary search, that's also why we use a vector instead of stack in the implementation.)

Coin Change (This textbook classic can also be solved by backtracking, but will be much more faster using tabulation.)

Coin Change 2 (This counts the number of ways to make up the given amount. dp[m][n] = dp[m][n-1] + dp[m-S[n]][n-1])

Matrix Multiplication (It is super painful for me to get the answer right, possibly because of the math issue:))

Target Sum (Another textbook classic)

Decode Ways (this is not a hard one, but great to practice for corner case thinking; )

Decode Ways II This is even more annoying by allowing wildcard and overflow. To handle the overflow, always mode for each step. Since the multiply then mod <=> mod then multiply.

Unique BST After the result F(n) should be the sum of different node as the roots, it is very useful to think of F(i, j) is the same as G(j - i). F(i, j) represent number of ways to construct BST starting from index i, and end at index j; while G(i) represent the ways to construct using number 0, 1, 2, ,,, i.

Unique Binary Search Trees II I created a 2D DP array to cache the subtree root initially, but it doesn't work eventually. Since you cannot have different parent pointing to the same left tree. Therefore, no cache is needed, each subtree is created on the fly.

Perfect SquaresUse tabulation method to solve it from bottom up. dp[i] = min(dp[i - m * m] + 1). This question is similar to Coin Change, Word Break: when fill the element, you must check all the possible available in order to decide the optimal one.

Flip Game This backtracking problem can easily be solved with memorizing the boolean of each possible s value.

---

2. 2-dim Maze problem. usually can be decomposed into dp[i][j] = max(func(dp[i -1][j]), func(dp[i][j - 1])), and reduce the 2d dp to 1D dp memory.

Unique Paths (The most classic maze problem)

Unique Paths II (The classic maze problem with obstacle, just need set the value of obstacle to be zero.)

Knight Probability in Chess (This looks really a tedious problem to me, but maybe i am not solving it favorably.)

Triangle (Using O(n) space, it is pretty simple.)

Word BreakThis is straightforward, using a one-dim dp, although i can reduce memory from O(n) to O(1)(How?? I forget.).

Word Break II ReConstruct the optimal solution from the dp[] created in Word break. So basically brute force. Not sure if any better solution.

Bond Enemy For each empty cell, we need to count the number of reachable enemy along row and col, The key point is to realize that we enermies between any two walls will be the same, So no need to update the enermy row; Same logic applies to cols. the count of enermies along rows and cols for each cell is cached, so => DP As a matter of fact, the more space DP representation can be rowCnt[i][j] = max(rowCnt[i][j-1] if grid[i][j-1] is not wall, 0)

Minimum Window Subsequence This is a hard question, but still can be solved with traditional dp. dp[i][j] represent the starting Idx of the matching if T[:j] is a subsequent of S[:i] and T[j] == S[i]. The remaining is just update the dp value by row.

3. inputs questions are two strings, the subproblem can reduced to s1[:i], s2[:j], hence it turns into a 2-dim dp matrix.

Longest Common Sequence

Edit Distance (The memory usage can be further reduce down to O(min(m, n)) using tabulation approach)

Min Path Sum (This is very similar to Edit Distance question, which works on a 2dim matrix and the memory can be further reduced to O(n)).

Min ASCII Distance (This is very similar to Edit Distance, except that the only operation here is delete)

Predict the Winner (This is very straightforward. The key point here is create a situation involving two parties.)

Regular Expression Matching when I solve it for the first time, I spent a lot of time handling corner case using backtracking. After seeing the official solution, it becomes clearer to me. 1) The first if else happens at compare the character two pointers are pointing to. If matching, (a) we can either move both by one step, or (b) just increase the pointer of string by one, if the next pointer in pattern is ''. 2). Second if-else happens when the next pointer in pattern is ''. (c) if the character of two pointers not match, can increase the pointer of pattern by two. else do (b). More elegantly, the problem can be memorized using dp[i][j] = whether s[:i] and p[:j] match.

Wildcard Matching This is very similar to the Regular Expression Matching problem and also solved in the same way. Similarly, this can also be solved through backtracking with memorization. The key point is to address the p[0] == *, in this case, dp[1, ... n][0] = true. when p[j] == *, dp[i][j] = dp[i+1][j] || dp[i][j+1].

---

4. Each element is a multi-dim array. In this case, always think about sorting element first and try to find ways to skip iterate all previous/later elements by utilizing the special feature of the problem. One textbook example is the stacking box problem.

For example:

Maximum Length of Pair Chain (Can be further reduce to O(n) using greedy + dp, with sorting at the begining)

---

5. States status is a change length list, if using dp[i][j][k][]... then it will be a high-dim problem. In this case, it is better to convert the list to a integer.

Shopping Offers

6. Problem involves include or not in an array. The solution here is separate out into two arrays/variables, each keeps track of hold or not.

Delete And Earn

Best Time to Buy Sell Stock with Fee

Best Time to Buy and Sell Stock with Cooldown The two lists holding here is buy[i] = max profit before time i if last transaction happened is buy. sell[i] = .... Noted that buy at the time i is not necessary.

Maximum Product SubarrayBasically, we keep track of the max and min ending in arr[i], if next element is negative, then we swap the min and max.

7. Convert the 1dim problem to 2dim, dp[idx][m]

Longest Palindromic Subsequence (the first dim record the starting index, the second dim record the ending index)

8. Others

Sentence Screen Fitting This is solved super smart by memorizing the dp[word index starting current row] = word index starting next row. And the dp table is also created by a very smart rolling window approach.

[Maximum Sum of 3 Non-Overlapping Subarrays](https://leetcode.com/problems/maximum-sum-of-3-non-overlapping- subarrays/description/) I am even not sure if this question falls into DP. The key is to reduce the problem from searching optimal i, j, l to just searching the middle index j and caching the position of largest left window before index j and the position of largest left window after index j.