Dynamic Programming

Four key points:

1. How to represent state
2. Formula(try all the possibilities, make decisions first)
3. Initialization
4. End State

Transform formula to iteration:

Difference between n->n-1 and n->n+1

1. If think about how to take the first step, you will get n->n+1. For example, in the computation of House Robber, it will be $f(i) = max(f(i+1),A[i]+f(i+2))$. In this case, f(i) means the most money you can get from i to n, so f(0) is the final result. f(i) is an unknown future or expectation of future.

2. If think about how to take the last step, you will get n->n-1. For example, in the computation of House Robber, it will be $f(i) = max(f(i-1),A[i]+f(i-2))$. In this case, f(i) means the most money you can get from 0 to i, so f(n) is the final result. f(i) is a fact that you already known.

3. Probably it's not always possible to transfer n->n+1 to n->n-1. But it has nothing to do for the computation process. The formula just represents the relationship between every state, which means if you do the initialization correctly, and do the computation in the right order(0->n/n->0), you can always get the same result.
4. If reversed input data can yield the same result, then you can change -/+ freely in the formula. Because in some cases, the first step you are gonna will determine

How to compute n->n+1 with iteration

1. Set up f(n), compute from n-1 to 0 and return f(0)
2. Compare to n->n-1, set up f(0), compute from 1 to n and return f(n)
3. It's normal to say a formula like this: $f(i,k) = max(f(i-1,k)+X,f(i-1,k-x))$. In such case, all f(i) only depend on f(i-1), which means you only need all K states in level i-1 to get level i. And therefore the space complexity is O(K).

How to minimize time complexity

1. Typical problem: Paint HouseII/ Backpack III/ Coins in a line III
2. Typical formula: $f(i,k) = max(f(i-1,k-n*C))(0<=n<(V/C))$
3. Since level i depends on sort of max value in level i-1, there will always be duplicate computations if you try to compute all values in level i with brute force. What you really need to do is figure out the max value once and do computation based on that which could reduce the time complexity for level i from O(K^2) to O(K).

Formulas:

Maximum Subarray: $f(i) = max\big\{f(i-1)+A[i],A[i]\big\}$

Maximum Subarray II: $f(i) = max\big\{ g(0,K)+g(K+1,n) \bigg\}(0<=K<n-1)$

Minimum Subarray: $f(i) = min\big\{f(i-1)+A[i],A[i]\big\}$

House Robber: $f(i) = max\big\{f(i-1),f(i-2)+A[i]\big\}$

Paint House: $f(i,c) = max\big\{ f(i-1,C_k)+A[i][c] \big\} (C_k!=c)$

Paint Fence: $f(i) = (k-1)*(f(i-1)+f(i-2))$

Backpack:

Backpack: $f(i,v)=max\bigg\{f(i-1,v),f(i-1,v-A[i])+A[i]\bigg\}$

=>$f(i,v)=max\bigg\{f(i-1,v-K*A[i])+K*A[i]\bigg\}(K=0||1)$

Backpack II:$f(i,v) = max\bigg\{f(i-1,v),f(i-1,v-A[i])+B[i]\bigg\}$

Backpack III:$f(i,v) = max\bigg\{f(i-1,v-K*A[i])+KB[i]\bigg\}(0<=K<V/A[i])$

=>$f(i,v)=max\bigg\{f(i-1,v),f(i,v-A[i])+B[i]\bigg\}$

Backpack IIII:

Double Sequence:

Edit Distance: $f(i,j) = min\bigg\{f(i+1,j+1)(equal) , f(i+1,j)+1(delete), f(i,j+1)+1(add), f(i+1,j+1)+1(replace)\bigg\}$

Distinct Subsequences:

Game theory:

Coins In a line: $f(i) = !f(i-1)||!f(i-2)$

Coins In a line II: $f(i) = max(A[i]+sum[i+1]-f(i+1),A[i]+A[i+1]+sum[i+2]-f(i+2))$

Coins In a line III: $f(i,j) = max(A[i]+sum[i+1,j]-f(i+1,j),A[j]+sum[i,j-1]-f(i,j-1))$ =>$f(i,j) = sum[i,j]-Math.min(f(i+1,j),f(i,j-1))$

Slicing DP:

Burst Balloon: f(i,j) = $max\big\{ f(i,K)+f(K,j)+A[i]*A[K]*A[j] \big\}(i<K<j)$