STRATEGY DYNAMIC PROGRAMMING

• Fibonacci Numbers:

  

  .

  • Recursive solution requires exponential time: has overlapping subproblems.
  • Bottom-up iterative solution is linear - compute once, store, and use many times.

• Matrix Sequence Multiplication
• Divide and Conquer Solution
• Recursive Formulation of M[i,j]
• Recursive Formula and Time Taken
• Matrix Parenthesization Order
• Work out