【题目描述】

有N个学生去食堂，可教官规定：必须2人或3人组成一组，求有多少种不同分组的方法。

【输入描述】

一个数，N。

【输出描述】

一个数，即答案。

【样例输入】

6

【样例输出】

2

【数据范围及提示】

N <= 150。

 

递推DP：

源代码：#include
       
        int n;long long f[151];int main(){    scanf("%d",&n);    f[2]=f[3]=1;    for (int a=4;a<=n;a++)      f[a]=f[a-2]+f[a-3];    printf("%lld",f[n]);    return 0;}
       

记忆化搜索DP：

源代码：#include
       
        int n;long long ans(0),f[151]={
     0}; //注意这坑人的Long Long。void Solve(int t){    if (f[t]) //记忆化。    {        ans+=f[t];        return;    }    if (!t) //成立。    {        ans++;        return;    }    long long num=ans;    if (t>=3)      Solve(t-3);    if (t>=2)      Solve(t-2);    f[t]=ans-num; //妙处之所在。改变即为此情况的答案。}int main(){    scanf("%d",&n);    Solve(n);    printf("%lld",ans);    return 0;}