斐波那契数列

看到这其实就是一个递归函数，然而纯递归须要大量反复的递归计算，超时

题目剖析


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。