解题思路

动态规划（DP）

定义 $dp[i][j]$ 表示第 $i$ 天吃菜 $j$（$1\leq j\leq m$）时的合法食谱数。

转移方程

• 第一天可以任意选，$dp[1][j]=1$。
• 后面每一天，$a_i$ 可以选 $j$，只要 $|a_{i-1} - j| \geq k$。

题目内容

小$A$很喜欢做饭,也很喜欢享用自己做的美食，但是小$A$希望每天吃的菜和前一天的口味不同，若两道菜的编号差不小于$k$，则小$A$认为这两道菜的口味是不同的，现在小$A$正在制定未来$n$天的食谐（第一天可以吃任何菜)，请问一共有几种合法的食谱。答案可能很大，输出结果请对$998244353$取模。