回文子序列计数

Count Palindromic Subsequences

问题：回文子序列计数

考察：字符串、动态规划

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/count-palindromic-subsequences

Problem: Count Palindromic Subsequences

Patterns: String, Dynamic Programming

Recency: 3mo

Link: https://leetcode.com/problems/count-palindromic-subsequences

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：区间 DP。令 dp[l][r] 表示子串 s[l..r] 的不同回文子序列数量，根据两端字符是否相等分情况转移；相等时还要寻找内部相同字符位置来避免重复计数。

复杂度：时间 O(n^2) 到 O(n^3)，取决于内部相同字符查找是否预处理；空间 O(n^2)。