共计 725 个字符，预计需要花费 2 分钟才能阅读完成。
斐波那契数列
看到这其实就是一个递归函数，然而 纯递归须要大量反复的递归计算，超时
题目剖析
1 办法会超时，须要计算大量数据
- 记忆化递归法：
在递归法的根底上，新建一个长度为 n 的数组，用于在递归时存储 f(0)f(0) 至 f(n)f(n) 的数字值，反复遇到某数字则间接从数组取用，防止了反复的递归计算。 -
动静布局：
以斐波那契数列性质 f(n+1)=f(n)+f(n-1)f(n+1)=f(n)+f(n−1) 为 转移方程。题解
-
记忆化递归法
首先新建一个长度为 n 的数组，用来存储 arr[0]-arr[n], 也就是 f(0)-f(n)的值为什么要对 1000000007 取模大数阶乘，大数的排列组合等，个别都要求将输入后果对 1000000007 取模 为什么总是 1000000007 呢 = = 大略≖‿≖✧是因为：（我猜的，不服你打我呀~）1. 1000000007 是一个质数 2. int32 位的最大值为 2147483647，所以对于 int32 位来说 1000000007 足够大 3. int64 位的最大值为 2^63-1，对于 1000000007 来说它的平方不会在 int64 中溢出 所以在大数相乘的时候，因为(a∗b)%c=((a%c)∗(b%c))%c，所以相乘时两边都对 1000000007 取模，再保留在 int64 外面不会溢出 ｡◕‿◕｡ - 动静规划法
不存入数组，间接求和，和始终在变 - 循环求余法：
大数越界：随着 n 增大, f(n)会超过 Int32 甚至 Int64 的取值范畴，导致最终的返回值谬误。
即，对因子取模后再取模和对最终后果取模的成果是一样的。题目中有个用 1000000007 取模，如果数字越界就取模 %1000000007，对 1e9+ 7 范畴内的数取模也是自身，没有影响，然而 100000008 取模后就等于 1。
正文完
