动态规划

https://blog.csdn.net/lxt_Lucia/article/details/80085527
转载
字串与子序列概念问题
字串：主串中连续的一段；
子序列：主串中取出相对位置不变的子序列；

已经解决的问题
1 求最长回文字串 枚举长度+枚举区间起点；
2 最长回文子序列 用小区间更新大区间；
未解决
1.求回文子序列个数

给定一字符串，求它的回文子序列个数。内容相同位置不同的子序列算不同的子序列。
例如字符串aba中，回文子序列为”a”, “a”, “aa”, “b”, “aba”，共5个。
字符串长度 s.length <= 50
思路：
区间型DP， 先来说一下状态方程： 如求i到j这个区间共有多少回文子序列 ，两种情况①当s[i] == s[j]时，例如“a….a”，d[i][j] = d[i][j-1] + d[i+1][j] + 1(由d[i][j] = 2d[i+1][j-1] + d[i][j-1] + d[i+1][j] + 1 - 2d[i+1][j-1] 化简来的。 解释：已知 i+1 到 j-1 有d[i+1][j-1]个回文子序列， 又有s[i] == s[j], 那么可与中间（串i+1到j-1）已知的回文子序列再构成d[i+1][j-1]个回文子序列，再加上原来中间串所包含的回文子序列共2d[i+1][j-1]个， 两个a组合”aa”也是回文, 所以再加1， 再分别计算左、右两边的a和中间串所构成的回文子序列， 但是这个时候还没完，注意：在分别计算左右两边a和中间串时，又算了两遍中间串包含的回文子序列， 所以在减去2*d[i+1][j-1]个)；②当s[i] != s[j]时，d[i][j] = d[i][j-1]+d[i+1][j] - d[i+1][j-1]。这个自己应该也能分析出来，和上面类似。

已解决：②当s[i] != s[j]时
d[i][j]=d[i+1][j-1]+d[i+1][j]+d[i][j-1]-2*d[i+1][j-1];.
=d[i+1][j]+d[i][j-1]-d[i+1][j+1];

求区间i到j时， 会用到d[i+1][j-1], d[i][j-1], d[i+1][j]。 这也正是为什么区间型DP一般都是从相距较小的区间开始， 然后不扩大区间。当下所求区间(i, j)所用的子区间，之前都已求完，so还是那句话，直接用就好啦。
那个地方意见不一致欢迎指出，互相学习！！
用dp[i][j]表示第i到第j个字符间的最长回文子序列的长度（i<=j），则状态转移方程为：
dp[i][j]=dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] ， if（s[i]！=s[j]）
dp[i][j]=dp[i+1][j] + dp[i][j-1] +1 ， if （s[i]==s[j]）***

总结DP还是利用 已经求得得小区间得答案值 来 更新大区间得答案值；
以及新增区间对小区间值造成的影响 在加上小区间本身的值 就可以得到大区间得答案；