注：本文目前只提供速记，不提供详解。
1. 5. 最长回文子串[五星]
状态：
令 dp[i][j] 表示子数组 s[i...j] 是否为回文子串。初始化 dp[i][i] = true，并且 dp[i][i+1] = (s[i]==s[i+1])。
状态转移方程：
代码：
// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)
class Solution {
public String longestPalindrome(String s) {
if(s.length() == 0) return "";
boolean[][] dp = new boolean[s.length()][s.length()];
// 初始化
int begin = 0, end = 0;
for(int i = 0; i < s.length(); i++) {
dp[i][i] = true;
if(i < s.length()-1) {
dp[i][i+1] = s.charAt(i) == s.charAt(i+1);
if(dp[i][i+1] && end - begin < 1) {
begin = i;
end = i + 1;
}
}
}
// 状态转移
for(int len = 2; len < s.length(); len++) {
for(int i = 0; i + len < s.length(); i++) {
int j = i + len;
dp[i][j] = dp[i+1][j-1] && s.charAt(i) == s.charAt(j);
if(dp[i][j] && end - begin < j - i) {
begin = i;
end = j;
}
}
}
return s.substring(begin, end+1);
}
}
2. 516. 最长回文子序列 [五星]
概念说明：
注意子串（substring）和子序列（subsequence）的区别，子串（substring）要求连续，子序列（subsequence）不要求连续。
状态：
令 dp[i][j] 表示 s[i...j] 中最长回文子序列的长度，初始化 dp[i][i] = 1。
状态转移方程：
代码：
// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
if(n == 0) return 0;
int[][] dp = new int[n][n];
// 初始化
for(int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 状态转移
for(int i = n-2; i >= 0; i--) {
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];
}
}
3、300. Longest Increasing Subsequence [五星]
4. 1143. Longest Common Subsequence [五星]
5. 10. Regular Expression Matching [五星+++]
6. 44. Wildcard Matching [五星+++]
7. 53. Maximum Subarray [五星]
8. 152. Maximum Product Subarray [五星++]
9. 62. Unique Paths
10. 63. Unique Paths II
11. 64. Minimum Path Sum [和62题是一样的]
12. 174. Dungeon Game
13. 741. Cherry Pickup [round trip, 暂时放弃...]
14. 120. Triangle [第64题的变形, 自底向上/自顶向下]
15. 509. Fibonacci Number
16. 70. Climbing Stairs
17. 746. Min Cost Climbing Stairs
18. 84. Largest Rectangle in Histogram [这一题不属于dp问题, 但是和85题是强相关的]
19. 85. Maximal Rectangle [五星++, 84题的follow-up]
20. 221. Maximal Square
21. 32. Longest Valid Parentheses [这一题比较独立, 五星++]