ABC130 E - Common Subsequence (500)
最初の解法
LCSの問題の解法に似ていそう
$ dp[i][j] で$ S_iと$ T_jをそれぞれの最後の文字にした時に作れる組み合わせとする
$ S_i \ne T_jの場合は0
それ以前の文字で作れた組み合わせの全てに$ S_iと$ T_jをつければ等しい組という条件は満たされたまま
$ dp[i][j] = \sum_{k=0}^{i} \sum_{l=0}^{j} dp[k][l] + 1 となる
$ O(N^2M^2)で間に合わない
高速化
これまでの和を計算する部分は累積和によって$ O(1)にできる
累積和の配列を$ ru[i][j] として、$ ru[i][j] = ru[i][j-1] + ru[i-1][j] - ru[i-1][j-1] + dp[i][j] で計算できる
$ S_i = T_j なら $ dp[i][j] = ru[i-1][j-1] となる
$ O(NM)となって間に合う