题目
思路
使用递归会重复计算子问题,考虑动态规划,对重复子问题进行缓存
Code
class Solution { public: int Fibonacci(int n) { if(n <= 1) return n; return Fibonacci(n-1) + Fibonacci(n-2); } }; class Solution { public: int Fibonacci(int n) { if(n <= 1) return n; int pre1 = 1 , pre2 = 0,res = 0; for(int i = 2; i <= n; i++) { res = pre1 + pre2; pre2 = pre1; pre1 = res; } return res; } };