花生米

来源：“歌尔创客杯”第二届哈尔滨理工大学（荣成）程序设计竞赛

题目

小Z有一包花生米一共有 m 粒，他一次可以吃下 1 粒、2 粒或 3 粒，请问小Z有多少种方法吃完一整包花生米？

解题思路

使用动态规划算法
令 dp[i] 表示吃下 i 粒花生的方法种数。
状态转移公式：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
dp[i-1] 表示最后一次吃的是第 i 粒 1 粒，dp[i-2] 表示最后一次吃的是第 i-1 和第 i 粒 2 粒，dp[i-3] 表示最后一次吃了 3 粒。
此时，空间复杂度为 。

dp优化：
因为 dp[i] 只与第 i 粒的前 3 中状态有关，所以可以使用 a、b 和 c 分别表示 3 中情况。这样，空间复杂度为 。

C++代码

#include<iostream>
using namespace std;

int main(){
    int n, m;
    cin >> n;
    while(n--){
        cin >> m;
        if(m==1){
            cout << 1 << endl;
            continue;
        }
        if(m==2){
            cout << 2 << endl;
            continue;
        }
        if(m==3){
            cout << 4 << endl;
            continue;
        }
        long long a = 1;
        long long b = 2;
        long long c = 4;
        long long cnt = 0;
        for(int i=4; i<=m; ++i){
            cnt = a + b + c;
            a = b;
            b = c;
            c = cnt;
        }
        cout << cnt << endl;
    }
    return 0;
}