Medium
实践证明，第一次没有彻底搞懂的题，第二次你还是会卡在 一样的地方。这道题当时我的记录是这样的：
image.png
我二刷卡在了index为什么要倒着走那里，结果我当时只写一句：不这么写的话后面会很麻烦。 这就是不理解还硬用，尴尬吧。还是要搞扎实一点啊，同学。
简单解释一下吧。因为后面我们求dp[i][j]需要用到dp[i+1][j-1]，dp[i+1][j], dp[i][j-1] 所以很明显我们的i需要从大到小，j需要从小到大来遍历。那i肯定最大是n-1,但j最小是不是0呢？肯定不是，随时记得dp方程表示的含义：dp[i][j]表示substring[i,j] (inclusively)所有最长回文子序列的长度，所以substring[i, j]确定了j至少得大于等于i。又因为我们单独处理了j== i的情况，所以j从i+1开始。而且这里我们为什么要把dp[i][i]单独提出来说呢？这是由于这个dp方程所代表的特殊含义决定的，我们不能用一般的转换方程去处理dp[i][i], 因为它代表的substring就是一个单独的char.
class Solution {
public int longestPalindromeSubseq(String s) {
if (s == null || s.length() == 0){
return 0;
}
int n = s.length();
//dp[i][j]: the length of the longest palindrome subsequence in substring[i, j] (inclusively)
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--){
dp[i][i] = 1;
//substring[i,j] stands for substring starting from i and ending at j both inclusively
//it's intuitive that j is equals to or greater than i, and since we
//speciafically talked about dp[i][i], j is sure to be greater than i in the inner for loop.
for (int j = i + 1; j < n; j++){
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][n - 1];
}
}