プログラミングコンテストチャレンジブック演習「最長共通部分問題」

今回のお題はこちら。

問題から漸化式をぱっと作れるようになりたいですなー。

require 'pp'

S = "abcd" #input
T = "becd" #input

$dp = Array.new( S.length + 1 ).map!{ Array.new( T.length + 1, 0 ) }
S.split('').each_with_index do |s, i|
  T.split('').each_with_index do |t, j|
    if s == t
      $dp[i + 1][j + 1] = $dp[i][j] + 1
    else
      $dp[i + 1][j + 1] = [$dp[i + 1][j], $dp[i][j + 1]].max
    end
  end
end

pp $dp