斐波那契数列：先用递归实现，分析其时空间复杂度，再优化为动态规划实现。请说说你的思路。

回答思路

1. 能正确写出递归实现并分析时间复杂度为 O(2^n)、空间复杂度为 O(n)（栈深度）
2. 指出递归重复计算问题，并引出动态规划或记忆化优化
3. 能实现 O(n) 时间、O(1) 空间的动态规划版本，说明状态转移方程
4. 能讨论边界条件（n=0、1）及可能的溢出问题