# 5 lines Top-down DP and 5 lines Bottom-up DP Solution in Java

• 5 lines Top-down DP Solution

``````public class Solution {
public int longestPalindromeSubseq(String s) {
int[][] dp = new int[s.length()][s.length()];
return longestPalindromeSubseq(s, 0, s.length() - 1, dp);
}

private int longestPalindromeSubseq(String s, int left, int right, int[][] dp) {
if(left > right) return 0;
if(dp[left][right] != 0) return dp[left][right];
dp[left][right] = (s.charAt(left) == s.charAt(right)) ? (left == right ? 1 : 2) + longestPalindromeSubseq(s, left + 1, right - 1, dp):
Math.max(longestPalindromeSubseq(s, left + 1, right, dp), longestPalindromeSubseq(s, left, right - 1, dp));
return dp[left][right];
}
}
``````

5 lines Bottom-up DP Solution

``````public class Solution {
public int longestPalindromeSubseq(String s) {
int[][] dp = new int[s.length()][s.length()];
for(int gap = 0; gap < s.length(); gap++)
for(int i = 0; i+gap < s.length(); i++)
dp[i][i+gap] = (s.charAt(i) == s.charAt(i+gap)) ? (gap == 0 ? 1 : 2 + dp[i+1][i+gap-1]) : Math.max(dp[i+1][i+gap], dp[i][i+gap-1]);
return dp[0][s.length()-1];
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.