**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)