How do you optimize Fibonacci computation using dynamic programming?

Naive recursion has O(2^n) complexity due to repeated subproblems. Memoization (top-down DP) stores computed values, reducing to O(n) time and O(n) space. Tabulation (bottom-up DP) iteratively fills a table from base cases: O(n) time, O(n) space. Space-optimized version only keeps last two values: O(n) time, O(1) space. Matrix exponentiation achieves O(log n) time using [[1,1],[1,0]]^n property.