858 群鸦的盛宴

题目链接：

思路

本题乍一眼看过去，你可能会想到使用一个二维数组A[51][51]来记录从i到j的路线数。

你很厉害，这是DP的思想。可是什么情况才用DP:分解得到子问题往往不是互相独立的。这也是DP和分治的最大区别之一。这题我从a走到b，和a之前b之后的格子完全没有关系啊！

so，冷静一下再看看，你会发现从1走到3和从2走到4其实是一样的，然后你会发现答案只与\(b-a\)有关。

举几个例子吧，1,2,3,5---卧槽，这是部分斐波那契啊，问题解决！

分析

通过举例子得到的规律只能帮你解题（这好像已经够了），有时候还有可能会错。

我们的问题是求从a到达b的路线数，令n=b-a，即求\(F(n)\)。有两种方式到达b，那就是从b-1和b-2过来，所以有\(F(n)=F(n-1)+(n-2)\)。

于是有\(F(1)=1,F(2)=2,...F(n)=F(n-1)+(n-2)\)。

另外，程序预处理数组，此题的查询复杂度为\(O(1)\)。

考点：斐波那契数列的转化与应用。

坑点：数据可能会超出int范围；请不要递归，预处理数组最佳。

参考代码

//// Created by AlvinZH on 2017/9/19.// Copyright (c) AlvinZH. All rights reserved.//#include 
    
     using namespace std;long long F[55];int n,a,b;int main(){    F[1]=1;    F[2]=2;    for (int i = 3; i <= 50; i++)//预处理        F[i] = F[i-1] + F[i-2];    scanf("%d",&n);    while (n--)    {        scanf("%d%d", &a, &b);        printf("%lld\n", F[b-a]);    }    return 0;}