DP类题目索引

1. 常数空间DP： 

　　53.152- 最大子序和/积   记录全局最优与当前最优

　　198/213 打家劫舍      记录 dp[i-2] dp[i-1]

2. O（n）空间DP：

　　300.最长上升子序列

　　279.完全平方数，具体参考第300题　　

　　　　求第n位，则把前n-1项的DP全求出来，最后通过状态转移方程求最后一项，如

　　　　dp[ 10 ] = max( dp[ 10 ] ,  dp[ i ] + 1)

　　96.不同的二叉搜索树

　　　　固定数量的二叉搜索树个数是固定的 G（n）

　　　　G(n) = i=1 ∑n​F(i,n)

　　

3. O（n^2）二维DP： 5.最长回文子串

　　DP[ i ][ j ] 代表 nums[ i : j ] 的子串

　　状态转移方程： dp[i][j] =  s[i] == s[j]  and dp[i+1][j-1]