c++实现最长回文子数组
时间: 2023-04-08 12:03:16 浏览: 85
可以回答这个问题。最长回文子数组可以使用动态规划算法来解决。具体方法是,定义一个二维数组dp,其中dp[i][j]表示从i到j的子数组是否为回文子数组。初始状态为dp[i][i]=true,即单个字符一定是回文子数组。然后,从长度为2的子数组开始,依次计算长度为3、4、5……n的子数组是否为回文子数组。具体计算方法是,如果s[i]==s[j]且dp[i+1][j-1]为true,则dp[i][j]也为true。最终,最长回文子数组的长度即为dp数组中最大的true对应的子数组长度。
相关问题
最长回文子序列递归的复杂度
最长回文子序列的递归复杂度是O(n^2)。这是因为在求解最长回文子序列的过程中,涉及到对每一个子序列进行判断和计算,而子序列的长度为n。因此,总的时间复杂度为O(n^2)。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [LeetCode:516 最长回文子序列](https://blog.csdn.net/chengda321/article/details/104523971)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *2* [516、最长回文子序列](https://blog.csdn.net/pengchengliu/article/details/92764961)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *3* [西电算法课程期末复习资料.zip](https://download.csdn.net/download/qq_42475914/12732528)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
[ .reference_list ]
C++力扣730统计不同回文子序列 程序代码
以下是 C++ 代码实现:
```cpp
class Solution {
public:
int countPalindromicSubsequences(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, -1));
const int MOD = 1e9 + 7;
function<int(int, int)> dfs = [&](int i, int j) -> int {
if (i > j) return 0;
if (i == j) return 1;
if (dp[i][j] != -1) return dp[i][j];
int res = 0;
if (s[i] != s[j]) {
res = dfs(i + 1, j) + dfs(i, j - 1) - dfs(i + 1, j - 1);
} else {
int l = i + 1, r = j - 1;
while (l <= j && s[l] != s[i]) l++;
while (r >= i && s[r] != s[i]) r--;
if (l > r) {
res = dfs(i + 1, j - 1) * 2 + 2;
} else if (l == r) {
res = dfs(i + 1, j - 1) * 2 + 1;
} else {
res = dfs(i + 1, j - 1) * 2 - dfs(l + 1, r - 1);
}
}
dp[i][j] = (res + MOD) % MOD;
return dp[i][j];
};
return dfs(0, n - 1);
}
};
```
时间复杂度为 O(n^2),空间复杂度为 O(n^2)。需要注意的是,为了避免数组下标越界,需要将 dp 数组初始化为 -1。