g*********e
发帖数: 14401 | 1 给定一个string，可以任意删除其中的char,以使的剩下的string成为palindrome,求最
长的这样
的palindrome。问有啥dp算法可以解？
有大侠帮忙指点一下吗 thx | z****e
发帖数: 2024 | 2 我靠，乱军中，还有你这坚守阵地的猛将！
【在 g*********e 的大作中提到】
: 给定一个string，可以任意删除其中的char,以使的剩下的string成为palindrome,求最
: 长的这样
: 的palindrome。问有啥dp算法可以解？
: 有大侠帮忙指点一下吗 thx
| g*********e
发帖数: 14401 | | f***g
发帖数: 214 | 4 哈哈
【在 z****e 的大作中提到】
: 我靠，乱军中，还有你这坚守阵地的猛将！
| i******0
发帖数: 609 | 5 Suppose the string length is N,
For any i, j such that 0<=i<=N-1, 0<=j<=N-1,
Ci is the character at index i, Cj is the character at index j
L(i, j) = the max length of the subsequence palindrome in the substring Ci...Cj
L(i, j) = 0 if i>j
L(i, j) = 1 if i==j
L(i, j) = 2 + L(i+1, j-1) if Ci == Cj
L(i, j) = max {L(i, j-1), L(i+1, j)} if Ci != Cj
L(0, N-1) will be the result you are looking for.
【在 g*********e 的大作中提到】
: 给定一个string，可以任意删除其中的char,以使的剩下的string成为palindrome,求最
: 长的这样
: 的palindrome。问有啥dp算法可以解？
: 有大侠帮忙指点一下吗 thx
| b***e
发帖数: 1419 | 6 这个题说过一千遍了：就是LCS(s, reverse(s))。这种加或减成palindrome的题都是
LCS.
Search: longest common sequence.
【在 g*********e 的大作中提到】
: 给定一个string，可以任意删除其中的char,以使的剩下的string成为palindrome,求最
: 长的这样
: 的palindrome。问有啥dp算法可以解？
: 有大侠帮忙指点一下吗 thx
| a******7
发帖数: 106 | |
|
