每日OJ题_牛客_最长回文子序列_区间DP_C++_Java

目录

牛客_最长回文子序列_区间DP

题目解析

C++代码

Java代码

牛客_最长回文子序列_区间DP

最长回文子序列_牛客题霸_牛客网 (nowcoder.com)

描述：

给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。

注：回文序列是指这个序列无论从左读还是从右读都是一样的。

本题中子序列字符串任意位置删除k（len(s)>=k>=0）个字符后留下的子串。

题目解析

基础的区间 dp 问题：

• 状态表示： dp[i][j] 表示：字符串 [i, j] 范围内的最长回文子序列的长度；
• 状态转移方程：
• 当 i == j 的时候，只有⼀个字符，长度为 1；
• 当 i < j 的时候，分情况讨论：
• s[i] == s[j]：dp[i][j] = dp[i + 1][j - 1];
• s[i] != s[j]：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])；
• 返回值： dp[0][n - 1] 。

C++代码

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    string str;
    cin >> str;
    int n = str.size();
    vector<vector<int>> dp(n, vector<int>(n));
    // dp[i][j] 表示i到j区间的最长回文子序列
    for(int i = n - 1; i >= 0; --i)
    {
        dp[i][i] = 1;
        for(int j = i + 1; j < n; ++j)
        {
            if(str[i] == str[j])
                dp[i][j] = dp[i + 1][j - 1] + 2;
            else
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[0][n - 1];
    return 0;
}

Java代码

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        char[] s = in.next().toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n];
        for(int i = n - 1; i >= 0; i--)
        {
            dp[i][i] = 1;
            for(int j = i + 1; j < n; j++)
            {
                if(s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        System.out.println(dp[0][n - 1]);
    }
}