動态規劃--吃糖果

題目大概：

每天可以吃一塊或者兩塊糖果，給出n塊糖果，問可以有幾種吃法。

思路：

根據題意，當吃到第n塊糖的時候，可以是吃1塊吃到第n塊，也可以吃2塊。是以當吃到第n塊的時候，他的方法數是吃n-1和n-2塊糖的方法數之和。

是以。

狀态：a[n]是吃第n塊糖的時候的方法數。

子問題：第n塊糖，最後是那種方法吃到的。有兩種。

狀态轉移方程：第n塊糖有兩種情況。

               1。。最後吃一塊糖 方法數a[n-1]的方法數

               2。。兩塊糖    方法數是a[n-2]的方法數。

a[n]=a[n-1]+a[n-2].

這怎麼像是斐波那契數列  這麼簡單。    qaq

感想：

代碼：

#include <iostream>

using namespace std;

int main()
{
int n,a[20];
a[1]=1;a[2]=2;
cin>>n;
for(int i=3;i<=n;i++)
{a[i]=a[i-1]+a[i-2];

}
cout<<a[n];
    return 0;
}