本文共 1414 字，大约阅读时间需要 4 分钟。
Objective-C实现最长回文子序列算法
在 Objective-C 中实现最长回文子序列（Longest Palindromic Subsequence，LPS）算法可以使用动态规划的方法。以下是一个完整的实现代码示例，以及详细的代码解释。
#import@interface Solution : NSObject(NSInteger)longestPalindromicSubsequence:(NSString *)s;@end@implementation Solution- (NSInteger)longestPalindromicSubsequence:(NSString *)s { if (s == nil || s.length == 0) { return 0; } // 定义动态规划表格，dp[i][j]表示子序列s[0..i-1]和s[j..n-1]的最长回文子序列长度 int n = s.length; int **dp = (int **)malloc(n * n); for (int i = 0; i < n; i++) { dp[i][i] = 1; // 单个字符的最长回文子序列长度为1 } // 遍历所有可能的子序列起始和结束位置 for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (s[i] == s[j]) { if (i == j) { dp[i][j] = 1; } else { dp[i][j] = dp[i+1][j-1] + 2; } } else { dp[i][j] = max(dp[i+1][j], dp[i][j-1]); } } } return dp[0][n-1];}@end
初始化动态规划表格：我们创建一个二维数组 dp，其中 dp[i][j] 表示子序列 s[0..i-1] 和 s[j..n-1] 的最长回文子序列长度。
处理单个字符的情况：当 i == j 时，单个字符的最长回文子序列长度为 1。
填充动态规划表格：遍历所有可能的子序列起始和结束位置 i 和 j。如果 s[i] 等于 s[j]，则 dp[i][j] 等于 dp[i+1][j-1] + 2（当前字符加上中间部分的最长回文子序列长度）。如果 s[i] 不等于 s[j]，则 dp[i][j] 取 dp[i+1][j] 和 dp[i][j-1] 中的最大值。
返回结果：最终的 dp[0][n-1] 即为字符串 s 的最长回文子序列长度。
通过动态规划的方法，我们可以高效地解决最长回文子序列问题。该算法的时间复杂度为 O(n^2)，适用于处理较短的字符串。对于更长的字符串，可以考虑使用更高效的算法如Manacher算法或中心扩展法。
转载地址：http://teifk.baihongyu.com/