如何編寫代碼實現一個字符串的最長回文子序列

本篇內容介紹了“如何編寫代碼實現一個字符串的最長回文子序列”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

import java.util.Arrays;

/**
 * @author pxu
 * @create 2021/4/7-5:57 下午
 */
public class Nc154 {
    

    public int longestPalindromeSubSeq (String s) {

        int n = s.length();
        /**
         * 在for循環運行過程中，dp[j]中的數據代表s從i到j的子串中的最長回文序列的長度
         * 在for運行結束后，dp[j]中的數據代表s從0到j的子串中的最長回文序列的長度，所
         * 以程序最后返回的結果就是dp[n-1]的值。
         */
        int[] dp = new int[n];

        /**
         * 填充為1的原因是，每一個字符都是一個長度為1的回文串
         */
        Arrays.fill(dp,1);

        for (int i = n-2;i>=0;i--) {

            /**
             * pre總是代表在字符串s從i+1到j-1的子串的最長的回文序列的長度，所以其初始值被設置為0
             */
            int pre=0;
            for (int j=i+1;j<n;j++) {
                /**
                 * 因為第i個字符可能會和第j個字符結合成回文對，導致原有dp[j]_old的值變為在dp[j-1]基礎上
                 * 增加2形成新的dp[j]_new，但是如果第i個字符也可以和第j+1個字符結合成回文對，這時候
                 * 對于第j+1個字符來說，第j個字符是沒有和第i個字符結合的（因為第i個字符，只能和后面的一個字符結合）
                 * ，所以dp[j+1]的新值應該是dp[j]的舊值的基礎上增加2得到。所以每次進入循環的時候需要把dp[j]的值
                 * 記錄在temp變量中，在本次循環結束之前，將值傳遞給pre，以便于在下一次循環中如果下一個字符也可以
                 * 和第i個字符結合時，更新dp中的值
                 */
                int temp = dp[j];
                if (s.charAt(i) == s.charAt(j)) {
                    dp[j] = pre + 2;
                }else {
                    dp[j] = Math.max(dp[j],dp[j-1]);
                }

                pre = temp;
            }
        }
        return dp[n-1];

    }

}

“如何編寫代碼實現一個字符串的最長回文子序列”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！