LeetCode: Distinct Subsequences

思路分析

还是明显的字符串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
comments powered by Disqus
Published:
2015-01-06
分类:
Tag:
DP15