Leetcode 509.斐波拉契数(动规 迭代和递归) 记录反思

也是动态规划的经典题目,利用前面几个值可以推出后面的值依次反复,这就是动规,虽然这个很简单
非常适合初学者入门动规
可以递归也可以迭代

//递归,真的很慢
class Solution {public int fib(int n) {if(n == 0)return 0;if(n == 1)return 1;if(n == 2)return 1;return fib(n - 1) + fib(n - 2);}
}
//迭代,快
class Solution {public int fib(int n) {if (n < 2) return n;int a = 0, b = 1, c = 0;for (int i = 1; i < n; i++) {c = a + b;a = b;b = c;}return c;}
}

非常适合初学者入门动规