DP 動态規劃 Problem K 1011 蜜蜂爬蜂房

Problem K  ID：1011

簡單題意：蜜蜂隻能爬向右側相鄰的蜂房，計算蜜蜂從蜂房a爬到蜂房b的可能路線數。      

解題思路形成過程：t=b-a為相隔的蜂房數。

            用一個數組a來儲存不同t值對應的可能路線數，a[1]=1，a[2]=2；

            當n>=3時，狀态轉移方程為：a[i]=a[i-1]+a[i-2]。

            因為0<a<b<50，進行預處理，将t=1至t=50的結果儲存到數組中。

            對應不同的t值，直接輸出對應的數組值（a[i]）。

感想：看似情況變複雜了，實際上隻比曾經遇到的問題（如上樓梯問題）多一步運算而已。

    當覺得情況有些陌生時，可以想一想是否和曾經遇到的問題相類似，能不能轉換成其他的問題。

    注意資料類型。

代碼：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
__int64 s[51];
void dp()
{
    s[1]=1;s[2]=2;
    for(int i=3;i<=50;++i)
        s[i]=s[i-2]+s[i-1];
}
int main()
{
    //freopen("1.txt","r",stdin);
    int n;
    scanf("%d",&n);
    dp();
    while(n--)
    {
        int a,b,t;
        scanf("%d%d",&a,&b);
        t=b-a;
        printf("%I64d\n",s[t]);
    }
    return 0;
}