经典的递归问题。
如果是自顶而下，会超时，应考虑自底而上，运用动态规划的思想。
我的两种解法： 1. 运用记忆数组 缓存已经得出的答案，加速递归时遇到大量重复的计算
map<int, int> m_Cached;
int fib(int n) {
if(n < 2)
{
m_Cached[n] = n;
return n;
}
auto iter = m_Cached.find(n);
if(iter != m_Cached.end())
{
return iter->second;
}
else
{
m_Cached[n] = (fib(n - 1) + fib(n - 2)) % 1000000007;
return m_Cached[n];
}
2.自底而上
int a,b,sum;
a= 0;
b=1;
sum =0;
for(int i = 0; i < n; ++i)
{
sum = (a + b)% 1000000007;
b = a;
a = sum;
}
return sum;
注：因为没看到题目中取余的要求，卡了好久。