题解（附滚动数组优化）

这题用一般的方法做如果将数组开在主函数外就会爆，因此我们把它开在主函数内(
普通解法：

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7, N = 1e7;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    long long dp[N] = {0, 1, 2, 4};
    cin >> n;
    for(int i=4;i<=n;++i)
        dp[i] = (dp[i-1]+dp[i-2]+dp[i-3])%mod;
    cout << dp[n];
}

当然，这题这么设计可能是为了考验我们的优化能力，因此我们可以使用滚动数组的方式来优化递推，这样就可以让空间复杂度大大降低，即使写在主函数外也不会爆
优化解法：

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int n;
long long dp[4] = {1, 2, 4};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i=4;i<=n;++i){
        dp[3] = (dp[2]+dp[1]+dp[0])%mod;
        dp[0] = dp[1]; dp[1] = dp[2]; dp[2] = dp[3];
    }
    cout << dp[3];
}