题解 | #斐波那契数列#
斐波那契数列
http://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3
第四十二题 都懒得写 和42一模一样
非递归
class Solution {
public:
int Fibonacci(int n) {
// 两种 一种递归 一种非递归
// 非递归效率高
if(n==1||n==2)
return 1;
int *a=new int[n];
a[0]=1;
a[1]=1;
for(int i =2;i<n;i++)
a[i]=a[i-1]+a[i-2];
return a[n-1];
}
};
public:
int Fibonacci(int n) {
// 两种 一种递归 一种非递归
// 非递归效率高
if(n==1||n==2)
return 1;
int *a=new int[n];
a[0]=1;
a[1]=1;
for(int i =2;i<n;i++)
a[i]=a[i-1]+a[i-2];
return a[n-1];
}
};
递归
class Solution {
public:
// 记录已经被计算出来的值
map<int,int> map_flag;
int Fibonacci(int n) {
// 两种 一种递归 一种非递归
// 递归
if(n==1||n==2)
return 1;
if(map_flag.count(n))
return map_flag[n];
map_flag[n]=Fibonacci(n-1)+Fibonacci(n-2);
return map_flag[n];
}
};
public:
// 记录已经被计算出来的值
map<int,int> map_flag;
int Fibonacci(int n) {
// 两种 一种递归 一种非递归
// 递归
if(n==1||n==2)
return 1;
if(map_flag.count(n))
return map_flag[n];
map_flag[n]=Fibonacci(n-1)+Fibonacci(n-2);
return map_flag[n];
}
};
题解 文章被收录于专栏
一遍做剑指offer 一边保存做题步骤 并附带详细注释哦
查看17道真题和解析
