動的計画法
に公開
に更新
1 min reads
LCS 数列 (あるいは文字列) \bold{a,b} の最長共通部分列 (longest common subsequence, LCS) の長さを O(|\bold{a}||\bold{b}|) で求めることができる。 \begin{aligned} dp_{0,j}&=dp_{i,0}=0\\ dp_{i+1,j+1}&=\begin{cases} dp_{i,j}+1&(\bold{a}_i=\bold{b}_j)\\ \max(dp_{i+1,j},dp_{i,j+1})&(\text{otherwise}) \end{cases} \end{aligned}\\[2ex] \text{where:}\\ 1\le i\le|\bold{a}|, 1\le j\le|\bold{b}|\\ dp_{i,j}:\{\bold{...