思路分析
还是明显的字符串DP,用dp[i][j]记录状态:从S的前i个字符中取子序列,组成T中前j个字符的不同方法数。这样的话,其实对于S中的每一个字符,显然地有取或者不取两种策略。由此得到对应的状态转移方程:
$$dp_{i, j} =
\begin{cases}
dp_{i-1, j}, S_{i} \neq T_{j} \\
dp_{i-1, j} + dp_{i-1, j-1}, S_{i} = T_{j}
\end{cases}$$
这题缺德的地方在于两个字符串最大长度差异很大,一个特别长,一个却又很短。由于C艹语言的动态分配二维数组很麻烦,很多时候都是直接静态分配全局空间,这时候就各种MLE和RE,挂了N多发才找到合适的数组大小,过了这个坑题。
代码
#define REP(i,a,b) for(int i=a;i