# 003 Dynamic Programming

# # 003 Dynamic Programming

#moc
*Dynamic Programming is a tool to solve problems which satisfy the
Principle of Optimality.*

## # Well Known Problems

- Fibonacci Sequence
- Longest Common Subsequence
- Chain Matrix Multiplication
- Knapsack Problem
- Travelling Salesman Problem

## # Strategies

Both strategies will achieve the same time complexity but bottom up is usually more CPU time efficient due to the simplicity of the code

### # Top Down Approach

- Formulate the problem in terms of recursive smaller subproblems.
- Use a dictionary to store the solutions to subproblems
- Turn the formulation into a recursive function
- Before any recursive call, check the store to see if a solution has been previously computed
- Store the solution before returning

Example with Fib DP:

### # Bottom Up Approach

- Formulate the problem in terms of recursive smaller subproblems.
- Draw the subproblem graph to find dependencies
- Use a dictionary to store the solutions to subproblems
- Turn the formulation into a recursive function
- Compute the solutions to subproblems first
- Use the solutions to compute the solution for P and store it

Example with Fib DP:

## # Exercises

#### # Binomial Coefficients

b. c. A top down approach: d. A bottom up approach