003 Dynamic Programming

Last updated Nov 7, 2022 Edit Source

• Moc

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

• Fibonacci Sequence
• Longest Common Subsequence
  • Longest Increasing Subsequence
  • Alignment Problem
• Chain Matrix Multiplication
• Knapsack Problem
  • Making Change
• Travelling Salesman Problem

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

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

Example with Fib DP:

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

Example with Fib DP:

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

• https://www2.seas.gwu.edu/~ayoussef/cs6212/dynamicprog.html