Longest Palindromic Subsequence

lps.rb

def lps(i, j)
  return $dp[i][j] if $dp[i][j]
  return 1         if i==j
  return 0         if i>j
  if $a[i] == $a[j]
    z = lps(i+1, j-1) + 2
  else
    z = [ lps(i+1, j), lps(i, j-1) ].max
  end
  $dp[i][j] = z
end

$dp = Hash.new []
$a = [1, 5, 2, 4, 3, 3, 2, 4, 5, 1]
p lps(0, $a.size-1)