前置:无
最低所需知识点:基础语法
这题经常用于动态规划入门的学习
但是不要害怕 这个非常简单 几乎小学生都知道如何推导
首先斐波那契前两个数分别为1 2
后面的每个数都是前面两个数的和
所以可以得出状态转移方程
dp[i]=dp[i-1]+dp[i-2];
当然注意for循环开始的下标 否则会数组访问越界 导致RE
观察数据 如果每次询问都重新演算 时间复杂度为q*log(x)时间差不多 但是我们有更加高效且难度不变的方法
我们需要一个全局数组用来存储足够的斐波那契数列
注意到x可以达到1e9而斐波那契的数呈指数级增长 所以大于如果你没有一个明确的下标 很有可能会导致溢出 从而错误判断
所以存储斐波那契的数组应为long long类型 当然 数组不用开的很大
经过实验计算 最多只需30即可使斐波那契中最大的数超过1e9
所以我们只需要推导30个数即可
对于每次询问 我们使用for循环遍历这大小只有30的数组 最坏时间复杂度为30q
q最大为1e5 不会超时 可以实现此题
------------------------------------------------------------题解结束------------------------------------------------------------
