Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:
"cbbd"
Output:
2
One possible longest palindromic subsequence is "bb".
思路：
說明
【基本問題單元的定義】這取決于你所查看問題的角度褐健，找到一個劃分，推進問題的角度十分重要进鸠。作者找到的方式是dp[ i ][ j ],用來表示 substring( i , j）盖呼，然后站在這個角度，假設(shè)substring(i , j )中的最大的結(jié)果是知道的褐缠，那么下一步需要確定的是懊直，其如何影響下一個階段的結(jié)果笔宿。
【遞推關(guān)系】在定義好了基本的問題單元之后质和，接下來就是用這個定義的單元去表示遞推關(guān)系稳摄。遞推關(guān)系反映了規(guī)模的逐漸擴大。（作者的在處理遞推的時候饲宿，會選擇是以兩個字符的方式遞推厦酬，或者是以一個的方式進行遞推）
【遞推的起點】以便其從開始點遞推下去。
【遞推的順序】確定以何種順序進行遞推瘫想，這樣子才能方便前面計算的結(jié)果為后面提供基礎(chǔ)弃锐，同時避免重復計算。
（問題單元）dp[i][j]: the longest palindromic subsequence's length of substring(i, j)
State transition（遞推關(guān)系）:
dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)
otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
（起點）Initialization:dp[i][i] = 1
但這個思路超時了殿托。。剧蚣。
還有最長公共子串參考了下附鏈接2 manacher
另外支竹，最長公共子序列旋廷，最長公共子串等，待續(xù)礼搁。饶碘。。
參考：
