2018-04-10 字符串最大回文子序列问题

最大回文子序列问题：使用动态规划做，初始化为: dp[i][i] = 1 递推公式为：

DP[i][j] = DP[i + 1][j - 1] + 2 (当 str[i] == str[j] 时) DP[i][j] = max(dp[i + 1][j], dp[i][j - 1]) (当 str[i] != str[j] 时)

int longestPalindromeSubSequence(String str) {

int[][] dp = new int[str.length][str.length];

for (int j = 0; j < n; j++) {
	dp[j][j] = 1;
	for (int i = j - 1; i >= 0; i--) {
		if (str.charAt(i) == str.charAt(j))
			dp[i][j] = dp[i + 1][j - 1] + 2;
		else
			dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
	}
}

return dp[0][str.length - 1];

}

有相应的其他问题: 求一个字符串中回文子序列的个数，还是用dp求解

int NumOfPalindromeSubSequence(String str) {

int[][] dp = new int[str.length][str.length];

for (int j = 0; j < str.length; j++) {
	dp[j][j] = 1;
	
	for (int i = str.length - 1; i >= 0; i--) {
		dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
		
		if (str.charAt(i) == str.charAt(j))
			dp[i][j] += 1 + dp[i + 1][j - 1];
	}
}

return dp[0][str.length - 1]; }

Written on April 10, 2018