题解 | #斐波那契数列#
斐波那契数列
https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ int Fibonacci(int n) { // write code here int a = 1; int b = 1; int now; if(n==1||n==2){ now = 1; } for (int i=2; i<n; i++) { now = a + b; a = b; b = now; } return now; } };
如果使用递归,则由于递归栈的重复运算,时间复杂度是O(2^n),空间复杂度是递归栈的深度O(n),效率很低。因此使用动态规划思路,将问题分解为子问题,将数列循环求和。