计数DP

将题目要求的两个序列以及要求转化成一个序列以及要求;
有一个序列A满足以下要求:

1. 长度为2 * ,
2. 非递减
3. a_i \in [1, n]

设f(i,j)为长度为i,最后一个数字为j的满足上述要求的序列的数量.
状态转移:f(i,j)=\sum_{k=1}^{j}dp[i-1][k],虽然时间复杂度较高,但是对于这个题目已经足够了.

for(int i = 2; i <= 2 * m; i ++)
        for(int j = 1; j <= n; j ++)
            for(int k = 1; k <= j ; k ++) 
            {
                dp[i][j] += dp[i-1][k];
                dp[i][j] %= MOD;
            }

考虑优化,利用扰动法,对于f(i,j-1)有,f(i,j-1)=\sum_{k=1}^{j-1}f(i-1,k),那么f(i,j)=f(i-1, j)+f(i,j-1),就优化到了两层循环嵌套.

for (int i = 2; i <= 2 * m; i ++)
    {
        for (int j = 1; j <= n; j ++)
        {
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] ) % MOD;
        }
    }