Dynamic programming has been one the hardest things for me to master. Why? Because it’s a totally different way of thinking that requires a different mindset when solving problems that can use dynamic programming.

So my way of learning dynamic programming is to just do many practice problems as possible to learn about all the tricks and try to apply it to future problems.

The following is a summary of various dynamic programming.

Max Value Contiguous Subsequence

$$T[i] = max \{T[i-1], T[i-1] + A_{i}\}$$

Making Change

$$T[i] = \min_{v_{j} < i} \{T(i-v_{j})\}$$

Longest Increasing Subsequence

$$T[i] = \max_{j < i}_{A[j] < A[i]]} \{T[j]\} + 1$$

Box Stacking

$$T[i] = \max_{j < i}_{D_j < D_i}_{w_j < w_i} \{T[j]\} + h_i$$

Billboards

$$T[i] = max \{T[i-1], T[opt(e)] + r_i\}$$

(Same as Weighted Value Schedule)

Weight Values Schedule

$$T[i] = max \{T[i-1], T[p(i)] + v_j\} p(j) = left most for j$$

Integer Knapsacks (Repeats)

$$T[i] = max \{T[i-1], \max_{w_j < i} \{T[i-w_j] + v_j\}\}$$

Integer Knapsacks (No Repeats)

Edit Distance

$$T[i,j] = min \begin{cases} C_d + T[i-1, j] \\ T[i, j-1] + C_i \\ \left\{\begin{matrix} T[i-1, j-1]& A[i] = B[j]\\ T[i-1, j-1] + C_R& A[i] \neq B[j] \end{matrix}\right. \end{cases}$$