class Solution {

  public int longestPalindromeSubseq(String s) {
    if (s == null || s.isEmpty()) {
      return 0;
    }

    int sLen = s.length();
    int[][] dp = new int[sLen][sLen];

    // Build the table for Dynamic Programming
    // Follow the formula, fill the table diagonally
    for (int k = 0; k < sLen; k++) {
      for (int i = 0; i < sLen; i++) {
        int j = i + k;

        if (j >= sLen) {
          continue;
        }

        if (i == j) {
          dp[i][j] = 1;
        } else if (s.charAt(i) == s.charAt(j)) {
          dp[i][j] = dp[i + 1][j - 1] + 2;
        } else {
          dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
        }
      }
    }

    return dp[0][sLen - 1];
  }

}