What is Dynamic Programming?
Dynamic Programming (DP) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems in a recursive manner. DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states. A sub-solution of the problem is constructed from previously found ones. DP solutions have a polynomial complexity which assures a much faster running time than other techniques.

Two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems.
a) a problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems.
b) a problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems.

To solve overlapping subproblems, there are two approaches:
1) Top-down approach
2) Bottom-up approach:

Four elements in Dynamic Programming
1. State (save results from subproblems)
2. Function ( the connection between states, how to get bigger states from small states)
3. Initialization (when is the start point – the smallest state)
4. Answer (when is the final point – the lagest state)

When to think about using DP
Note: 98% accurate, not 100%
1. One of the following situations
a) find maximum / minimum
b) yes / no question
c) count all possible solutions

2. The elements in the problem cannot be sorted / swapped

Normal DP problems:
1. matrix
2. sequence
3. two sequences DP
4. backpack

Analysis

1. Matrix DP
state: f[x][y] – from start point to (x,y) position
function: investigate the step before get to (x,y) position
initialize: start point
answer: end point

Sample question 1:
in a matrix, find minimum path sum
State: f(x,y) is the shortest path by starting from the start point to x, y (walk down or right only)

Function: f(x,y) = min(f(x-1,y), f(x,y-1)) + matrix_element(x,y)

initialize:
f(0,0) = matrix_element(0, 0)
f(i,0) = sum(matrix_element(0, 0), matrix_element(1, 0), …, matrix_element(i, 0))
f(0,j) = sum(matrix_element(0, 0), matrix_element(0, 1), …, matrix_element(0, j))

answer: f(m-1, n-1)

Sample question 2:
in a matrix, find the unique path (walk down or right only) from left top corner to the right bottom corner a(0, 0) to a(m-1,n-1)

State: f(x,y) is the unique path by starting from the start point to x, y

Function: f(x,y) = f(x-1,y) + f(x,y-1)

initialize:
f(0,0) = 1
f(i,0) = 1
f(0,j) = 1

answer: f(m-1, n-1)