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