经典递推题，dp[i][j] 表示第 i 天，已感染 j 天的人数。dp[i][0]其实就是当天的有症状感染者数量。

d[i][0] = (d[i - 1][0] + d[i - 1][2])
d[i][1] = d[i - 1][0];
d[i][2] = d[i - 1][1];

还算比较简单

#include <iostream>
using namespace std;
const int M = 1000000007;
long long n,sum=1,day1,day2,t;
int main()
{
    cin>>n;
    for(int i = 1;i <= n;i++)
    {
        t = day2;
        day2 = day1;
        day1 = sum;
        sum += t;
        sum %= M;
    }
    cout<< (sum+day1+day2)%M;
    return 0;
}

思路 代码

#include <iostream>
using namespace std;
long long a[1001],b[1001],c[1001],d[1001],n;
int main()
{
    cin>>n;
    a[1]=1;
    b[1]=1;
    for (int i=2;i<=n;i++)
    {
        a[i]=(a[i-1]+d[i-1])%1000000007;//有症状=前一天有症状+前一天感染两天
        b[i]=a[i]%1000000007;//当天感染=当天有症状
        c[i]=b[i-1]%1000000007;//感染一天=前一天的当天被感染
        d[i]=c[i-1]%1000000007;//感染两天=前一天的感染一天
    }
    cout<<(a[n]+b[n]+c[n]+d[n])%1000000007;
}

很明显，这题输入输出都只有一个数。

那么，一种O(1)复杂度的伟大思想就能被用上了……

打表

定义数组ans，ans[i]是输入为i时的输出。

适用范围有极限，n过大时易UKE（代码过长无法提交，提交了也没法评测）或MLE。

时间复杂度 O(1),空间O(n).

对本题来说，ans数组为:

ans={0,1,3……};//剩余部分不作展示

打表法中，主函数恒为：

int n;
cin>>n;
cout<<ans[n];
return 0;

大概就是这样。

打表虽好，不能乱用，否则等待你的将是爆零的命运。

看到题解里有比我更简单的但是不知道效率怎么样（）
也许代码比其他题解复杂但也许更好理解？
平均内存占用400kb以下，耗时1ms。

struct Inf{
    long long asy,oneDay,twoDay,threeDay;
}inf[1002];

搞个结构体然后算就得了，算的过程还要不断取模，不然容易越界，类型要long long

    inf[0].asy=1;
    for(short i=1;i<=n;i++){
        inf[i].asy=(inf[i-1].asy+inf[i-1].threeDay)%mod;
        inf[i].threeDay=inf[i-1].twoDay;
        inf[i].twoDay=inf[i-1].oneDay;
        inf[i].oneDay=inf[i].asy;
    }

最后输出的时候把inf[n]的所有成员相加并且取模就行了。
如果结构体里面的三个Day想用数组代替（比如day[3]）的话，编译器必须得C++11及以上才行，98没结构体动态数组这特性，运行会报错。

感染n天后的总人数就是有症状的+感染1天的+感染2天的。

有症状的就是前一天有症状的+前一天感染2天的人数。

感染一天的就是前一天有症状的人数

感染两天的就是前一天感染一天的人数。

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。