f[i][j] means string[i...j] is palindromic.
thus, f[i][j] = true if str[i] == str[j] && f[i + 1][j - 1] = true
Longest Palindromic Subsequence
g[i][j] means the maximum length of palindromic subsequence in string[i...j]
thus, g[i][j] = max(g[i + 1][j - 1] + 1 (if str[i] == str[j]),
g[i + 1][j],
g[i][j - 1]);
没有评论:
发表评论