本文从WordPress迁移而来, 查看全部WordPress迁移文章
【重做DP系列】 字符串DP,记忆化搜索实现
【2013多校联合训练第四场】
题意:给定一个字符串,找出里面有多少个回文子序列
dp[i][j]表示i到j之间有多少个回文子序列,目标状态是dp[0][n-1]
不取前一个字符能产生的回文子序列,dp[i+1][j]
不取后一个字符能产生的回文子序列,dp[i][j-1]
不取前后两个字符能产生的回文子序列,dp[i+1][j-1]
那么 dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1],减去是因为减掉重复的部分
如果str[i] = str[j],那么加上这两个依然是一个回文串
dp[i][j] += ( dp[i+1][j-1] + 1)
这是个区间dp,递推和递归实现都可以,递推快一些,递归容易理解容易写
1 |
|