题面

Python 中语句块并没有大括号包围，而是靠缩进来定义的。

现在有一种简化版的 Python，只含有两种语句：

  • s：Simple statement，即一般的语句。
  • f：For statement，即循环语句（相当于 for），并且其循环体不可为空。

现在给你一段没有缩进的这种简化版 Python 的代码，请你计算有多少种合法的 Python 程序。

题目链接

动态规划！

我们来看看第 nn 行语句。不管第 nn 行语句是哪类语句，其可能的缩进实际上完全取决于第 n−1n - 1 行：

  • 若第 n−1n - 1 行是 f ，第 nn 行的缩进只可能比第 n−1n - 1 行多 1；
  • 若第 n−1n - 1 行是 s ，第 nn 行的缩进可以是 0 ~ 第 n−1n - 1 行缩进中的任意一值（即小于等于 n−1n - 1 行的缩进）。

基于此发现，我们可以用 dp[i][j]dp[i][j] 表示状态，表示第 ii 行缩进为 jj 时的方案个数。边界条件即 dp[0][0]=1dp[0][0] = 1 。

同时，我们也不难推出状态转移方程：

  • 若第 i−1i - 1 行为 f，那么第 ii 行缩进为 jj 的情况种数实际上等于第 i−1i - 1 行缩进为 j−1j - 1 的情况种数：

    dp[i][j]=dp[i−1][j−1] dp[i][j] = dp[i - 1][j - 1]

  • 若第 i−1i - 1 行为 s，那么第 ii 行的缩进一定是小于等于第 i−1i - 1 行的缩进。反过来看，也就是说第 ii 行缩进为 jj 的情况种数是第 i−1i - 1 行缩进为 jj , j+1j + 1 … 一直到最大可能的缩进值的所有方案数之和（由于只有 f 语句可能带来缩进，所以最大缩进值就是之前语句中 f 的个数，下面公式中记作 MM ）。 dp[i][j]=∑k=jMdp[i−1][k] dp[i][j] = \sum\limits_{k = j}^{M} dp[i - 1][k]

那么最后我们所要求的总合法方案数就是（同样记最大可能缩进为 MM ）：

∑k=0Mdp[i][k] \sum\limits_{k = 0}^{M} dp[i][k]

具体实现？

朴素实现

Submission #33981342

算法复杂度达到了 O(n3)\mathcal{O}(n^3) ，不 TLE 才怪……

树状数组维护前缀和

可以参考一下 Leohh 大佬的博文： 链接

倒着循环维护后缀和

Submission #33983065

刚才的朴素算法主要是在处理第二种情况（第 i−1i - 1 行为 s ）时复杂度高了，其原因则是因为求和的过程中做了很多重复运算。我们发现：

dp[i][0]=dp[i−1][0]+dp[i−1][1]+...+dp[i−1][M]dp[i][1]=dp[i−1][1]+dp[i−1][2]+...+dp[i−1][M]...dp[i][M]=dp[i−1][M] \begin{aligned} & dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + ... + dp[i - 1][M] \\ & dp[i][1] = dp[i - 1][1] + dp[i - 1][2] + ... + dp[i - 1][M] \\ & ... \\ & dp[i][M] = dp[i - 1][M] \end{aligned}

因此我们没有必要在计算每一个 dp[i][j]dp[i][j] 时都把 ∑k=jMdp[i−1][k]\sum\limits_{k = j}^{M} dp[i - 1][k] 算一遍，只需要维护一个后缀和就可以了。

int suffixSum = 0;
for (int j = maxIndentation; j >= 0; j--)
{
    suffixSum += dp[i - 1][j];
    suffixSum %= mod;
    dp[i][j] = suffixSum;
}

%%%