排队问题

【题目描述】

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

【输入描述】

一个数，N。

【输出描述】

一个数，即答案。

【样例输入】

6

【样例输出】

2

【数据范围及提示】

N <= 150。

递推DP：

源代码：

#include<cstdio>
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<cstdio>
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;
}