【JZOJ 5195】【NOIP2017提高组模拟7.3】A (dp)

问题描述

输入

输出

数据范围

样例输入
7 3
样例输出
4
算法讨论

#include <cstdio>
#define MAX_N 5006
#define mo 998244353
using namespace std;
int f[MAX_N][MAX_N],n,k;

int main()
{
    scanf("%d%d",&n,&k);
    f[1][1]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=k;j++)
        {
            if ((i-1)>0 && (j-1)>0)
                f[i][j]=(f[i][j]+f[i-1][j-1]) % mo;
            if (i-j>0)
                f[i][j]=(f[i][j]+f[i-j][j]) % mo;
        }
    printf("%d",f[n][k]);
}