Question

杭电ACM2044 递推题的详细解答思路

我想知道怎么得出 菲薄纳 数列。。还有详细的思路。

Answer 1

//观察一下那张图就得到了递推式

假设从i走到j，那么当j-i<=1时肯定只有1种方法，否则就dp[i][j]=dp[i][j-1]+dp[i][j-2];比如说从1走到5的方法数，如果我们已经知道了从1走到3和从1走到4的方法数，二者加起来不就是从1走到5的方法数，因为3和4都能1步到达5

　#include<stdio.h>

　　#include<string.h>

　　__int64 dp[51][51];

　　int main()

　　{

　　int i,j;

　　for(i=0;i<50;i++) dp[i][i]=1;

　　for (i=1;i<50;i++)

　　{

　　dp[i][i+1]=1;

　　for (j=i+2;j<50;j++)

　　{

　　dp[i][j]=dp[i][j-1]+dp[i][j-2];

　　}

　　}

　　int n;

　　scanf("%d",&n);

　　while(n--){

　　int a,b;

　　scanf("%d%d",&a,&b);

　　printf("%I64d\n",dp[a][b]);

　　}

　　}