Codeforces 1000D(DP+组合数)

Codeforces 1000D
题意：定义一个序列是“好的”：第一个数字$a_0$为序列长度$+1$。定义一个序列的子序列是“好的”：这个子序列能分割成几个“好的”序列。给出一个序列，求“好的”子序列的数目。

一开始我想把所有这种序列全部求出来然后组合。。具体就是每个点往后面找，用组合数。然后再合并。但是行不通。。
这题直接从后面往前面 DP 即可。设$dp(i)$为$[i, n]$“好的”子序列个数。我们这样定下来了左端点，再枚举一个右端点$j$，使当前所有“好的”序列最后一个是$j$，那么和$j$后面已经算完的 DP 值乘起来即可。

可能直接初值$dp(n+1)=1$，转移$dp(i)=dp(j) \times C(j-i-1,a_i)$更好？

知识点：
1、DP 从后往前

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 1000 + 5;
    const LL MO = 998244353;

    int n, a[MAXN];
    LL c[MAXN][MAXN], dp[MAXN], suf[MAXN];

    void clean() {
        ms(dp, 0), ms(suf, 0);
    }
    int solve() {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        clean();

        for (int i = 0; i <= n; ++i) c[i][0] = c[i][i] = 1;
        for (int i = 1; i <= n; ++i) 
        for (int j = 1; j < i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MO;

        //                                for (int i = 0; i <= n; ++i, cerr << endl) 
        //                                for (int j = 0; j <= i; ++j) cerr << c[i][j] << " ";

        LL ans = 0ll;
        for (int i = n; i; --i) {
            if (a[i] > 0 && i + a[i] <= n) 
            for (int j = i + a[i]; j <= n; ++j) {
                dp[i] = (dp[i] + (c[j - i - 1][a[i] - 1] * (1ll + suf[j + 1])) % MO) % MO;
            }
            suf[i] = (suf[i + 1] + dp[i]) % MO;
        }

        cout << suf[1];

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}