最長共通部分列問題

longest_common_subsequence.rb

## 最長共通部分列問題
## http://rubyfiddle.com/riddles/10ea3

s = "abcd"
t = "becd"
n = s.length
m = t.length

dp = Array.new(n+1,0).map{Array.new(m+1,0)}

n.times{|i|
  m.times{|j|
    if s[i] == t[j]
      dp[i+1][j+1] = dp[i][j]+1
    else
      dp[i+1][j+1] = [dp[i][j+1],dp[i+1][j]].max
    end
    }
  }
puts dp[n][m]