C++ 解法, 执行用时: 72ms, 内存消耗: 39612K, 提交时间: 2022-01-16 12:11:53

#include<stdio.h>
int main()
{
	int a[10000001]={0,1,2,3};
	int x,i;
	scanf("%d",&x);
	for(i=4;i<=x;++i)
	{
		a[i]=a[i-1]+a[i-3];
		a[i]=a[i]%1000000007;
	}
	printf("%d",a[x]);
	return 0;
}

pypy3 解法, 执行用时: 707ms, 内存消耗: 182360K, 提交时间: 2021-12-26 21:59:44

mod=1e9+7
ans=[0,1,2,3]
x=int(input())
ans=ans+[0]*x
if x<=3:
    print(ans[x])
else:
    for i in range(4,x+1):
        ans[i]=(ans[i-1]+ans[i-3])%mod
    print(int(ans[x]%mod))

C 解法, 执行用时: 67ms, 内存消耗: 39544K, 提交时间: 2022-12-18 13:37:48

#include<stdio.h>
int main()
{
    int i,s[10000000]={0,1,2,3},x;
    scanf("%d",&x);
    for(i=4;i<=x;i++)
        s[i]=(s[i-1]+s[i-3])%1000000007;
    printf("%d",s[x]);
}