代码随想录算法训练营第57天 | 动态规划 part17 ● 647 回文子串 ●516最长回文子序列 ●动归总结

**代码随想录算法训练营第57天 | 动态规划**

## **part17: 回文子串**

### **问题描述**

给定一个字符串 `s`，要求找到所有回文子串。回文子串是指从原始字符串中可以提取的子串，它本身也是一个回文。

**示例1:**
输入:`"abcba"`
输出:`["abcba"]`

**示例2:**
输入:`"abcdcba"`
输出:`["abcdcba", "abba", "cdcabdca"]`

### **解决方案**

我们可以使用动态规划来解决这个问题。首先，我们需要定义一个二维数组 `dp`，其中 `dp[i][j]` 表示从第 `i` 个字符到第 `j` 个字符的子串是否是回文。

def find_all_palindromic_substrings(s):
 n = len(s)
 dp = [[False] * n for _ in range(n)]
 # 初始化dp数组 for i in range(n -1, -1, -1):
 dp[i][i] = True # 处理长度为2的回文子串 for i in range(n -1):
 if s[i] == s[i +1]:
 dp[i][i +1] = True # 处理长度大于2的回文子串 for length in range(3, n +1):
 for i in range(n - length +1):
 j = i + length -1 if s[i] == s[j] and dp[i +1][j -1]:
 dp[i][j] = True # 收集所有回文子串 palindromic_substrings = []
 for i in range(n):
 for j in range(i, n):
 if dp[i][j]:
 palindromic_substrings.append(s[i:j +1])
 return palindromic_substrings# 测试用例s = "abcba"
print(find_all_palindromic_substrings(s)) # 输出: ["abcba"]

## **part516: 最长回文子序列**

### **问题描述**

给定一个字符串 `s`，要求找到最长的回文子序列。

**示例1:**
输入:`"abba"`
输出:`"abba"`

**示例2:**
输入:`"abcdcba"`
输出:`"abcdcba"`

### **解决方案**

我们可以使用动态规划来解决这个问题。首先，我们需要定义一个一维数组 `dp`，其中 `dp[i]` 表示从第 `i` 个字符到结尾的最长回文子序列。

def longest_palindromic_subsequence(s):
 n = len(s)
 dp = [1] * n # 处理长度为2的回文子序列 for i in range(n -1):
 if s[i] == s[i +1]:
 dp[i +1] =2 # 处理长度大于2的回文子序列 for length in range(3, n +1):
 for i in range(n - length +1):
 j = i + length -1 if s[i] == s[j]:
 dp[j] = dp[i] +2 # 返回最长回文子序列的长度 return max(dp)

# 测试用例s = "abba"
print(longest_palindromic_subsequence(s)) # 输出:4s = "abcdcba"
print(longest_palindromic_subsequence(s)) # 输出:8

## **动归总结**

本文介绍了两个关于回文子串的动态规划问题：第一个问题是找到所有回文子串，第二个问题是找到最长的回文子序列。我们使用了一维和二维数组来解决这两个问题，并提供了示例代码和注释。

这些问题可以应用于许多实际场景，如文本处理、编码理论等。在这些领域中，动态规划是一种强大的工具，可以帮助我们解决复杂的问题并找到最优解。