算法27：最長(zhǎng)回文子序列長(zhǎng)度——范圍模型

這篇具有很好參考價(jià)值的文章主要介紹了算法27：最長(zhǎng)回文子序列長(zhǎng)度——范圍模型。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

題目：

樣本模型：

遞歸版本的范圍模型

分析過(guò)程

動(dòng)態(tài)規(guī)劃版本

優(yōu)化動(dòng)態(tài)規(guī)劃：

題目：

給定一個(gè)字符串str，返回這個(gè)字符串的最長(zhǎng)回文子序列長(zhǎng)度

比如?str = “a12b3c43def2ghi1kpm” * 最長(zhǎng)回文子序列是“1234321”或者“123c321”，返回長(zhǎng)度7

這一題使用樣本模型，也可以解決，只需要生成一個(gè)逆序字符串就可以了。因?yàn)榛匚淖有蛄校嫘蛞院?，回文子序列依舊保持原來(lái)的順序結(jié)構(gòu)。

樣本模型：

遞歸版本：

public static int longestPalindromeSubseq(String s)
    {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        char[] s1 = s.toCharArray();
        char[] s2 = new char[s1.length];
        int position = 0;
        //生成逆序
        for (int i = s1.length-1; i >=0; i--) {
            s2[position++] = s1[i];
        }

        return process(s1, s2, s1.length-1, s2.length-1);
    }

    public static int process(char[] s1, char[] s2, int i, int j)
    {
        if (i == 0 && j == 0){
            return s1[i] == s2[j] ? 1 : 0;
        }
        else if (i == 0) {
            return  s1[i] == s2[j] ? 1 : process(s1, s2, i, j-1);
        }
        else if (j == 0) {
            return  s1[i] == s2[j] ? 1 : process(s1, s2, i-1, j);
        }
        else {

            int p1 = process(s1, s2, i, j-1);

            int p2 = process(s1, s2, i-1, j);

            int p3 = s1[i] == s2[j] ? process(s1, s2, i-1, j-1) + 1 : 0;

            return Math.max(p1, Math.max(p2, p3));
        }
    }

測(cè)試結(jié)果：

算法27：最長(zhǎng)回文子序列長(zhǎng)度——范圍模型

動(dòng)態(tài)規(guī)劃版本：?

package code03.動(dòng)態(tài)規(guī)劃_07;

/**
 * 給定一個(gè)字符串str，返回這個(gè)字符串的最長(zhǎng)回文子序列長(zhǎng)度
 * 比如 ： str = “a12b3c43def2ghi1kpm”
 * 最長(zhǎng)回文子序列是“1234321”或者“123c321”，返回長(zhǎng)度7
 *
 * https://leetcode.com/problems/longest-palindromic-subsequence/
 */
public class PalindromeSubsequence_05
{
    public static int longestPalindromeSubseq(String str) {

        if (str == null || str.isEmpty()) {
            return 0;
        }
        char[] s1 = str.toCharArray();
        char[] s2 = new char[s1.length];
        int position = 0;
        //生成逆序
        for (int i = s1.length-1; i >=0; i--) {
            s2[position++] = s1[i];
        }

        //以s1做行，s2做列
        int[][] dp = new int[ s1.length][s2.length];

        int index1 = s1.length - 1;
        int index2 = s2.length - 1;

        //根據(jù)遞歸   if (index1 == 0 && index2 == 0)  而來(lái)
        dp[0][0] = s1[0] == s2[0] ? 1 : 0;

        //根據(jù)遞歸  else if (index1 == 0)  而來(lái), 此處代表先處理 第一行的所有列
        for (int i = 1; i <= index2; i++) {
            dp[0][i] = s1[0] == s2[i] ? 1 : dp[0][i-1];
        }

        //根據(jù)遞歸  else if (index2 == 0)  而來(lái), 此處代表先處理 第一列的所有行
        for (int j = 1; j <= index1; j++) {
            dp[j][0] = s1[j] == s2[0] ? 1 : dp[j-1][0];
        }

        //通用case  根據(jù)遞歸中最后一個(gè)else而來(lái)
        for (int row = 1; row <= index1; row++) {
            for (int col = 1; col <= index2; col++) {

                //根據(jù) int p1 =  process(s1, s2, index1, index2-1) 改寫(xiě)
                int p1 = dp[row][col - 1];

                //根據(jù) int p2 =  process(s1, s2, index1-1, index2) 改寫(xiě)
                int p2 = dp[row -1][col];

                //int p3 = s1[index1] == s2[index2] ? (process(s1, s2, index1-1, index2-1) + 1) : 0;
                int p3 = s1[row] == s2[col] ? (dp[row -1][col -1] + 1) : 0;

                dp[row][col] = Math.max(p1, Math.max(p2, p3));
            }
        }

        //返回值對(duì)應(yīng)遞歸中的下標(biāo)
        return dp[index1][index2];
    }
}

算法27：最長(zhǎng)回文子序列長(zhǎng)度——范圍模型

樣本模型，在上一篇已經(jīng)詳細(xì)的說(shuō)過(guò)了，具體推導(dǎo)過(guò)程可以參照?算法27：最長(zhǎng)公共子序列——樣本模型（4）_chen_yao_kerr的博客-CSDN博客

樣本模型，都是以樣本的最后一個(gè)元素為基礎(chǔ)進(jìn)行討論分析的。

而范圍模型，則是以樣本數(shù)據(jù)的? 開(kāi)頭? 和? 結(jié)尾? ?進(jìn)行討論的。

遞歸版本的范圍模型

package code03.動(dòng)態(tài)規(guī)劃_07;

/**
 * 給定一個(gè)字符串str，返回這個(gè)字符串的最長(zhǎng)回文子序列長(zhǎng)度
 * 比如 ： str = “a12b3c43def2ghi1kpm”
 * 最長(zhǎng)回文子序列是“1234321”或者“123c321”，返回長(zhǎng)度7
 *
 * https://leetcode.com/problems/longest-palindromic-subsequence/
 */
public class PalindromeSubsequence_05_opt1
{
    public static int longestPalindromeSubseq(String str)
    {
        if (str == null || str.isEmpty()) {
            return 0;
        }

        return process(str.toCharArray(), 0, str.length() -1);
    }

    //范圍模型，需要討論樣本數(shù)據(jù)的開(kāi)頭和結(jié)尾
    public static int process(char[] str, int left, int right)
    {
        //如果長(zhǎng)度為1,也就是說(shuō)字符串只有一個(gè)字符
        if (left == right) {
            return 1;
        }

        //字符串只有2個(gè)元素. 如果第一個(gè)元素和第二個(gè)元素相同，則說(shuō)明回文
        //長(zhǎng)度為2. 否則，最長(zhǎng)子回文只有1，因?yàn)槲覀兡J(rèn)的子序列回文長(zhǎng)度就是為1.
        if (left == right -1) {
            return str[left] == str[right] ? 2 : 1;
        }

        /**
         * 最長(zhǎng)回文子序列, 有可能出現(xiàn)以下情況
         * 1. 包含結(jié)尾，不包含開(kāi)頭
         * 2. 包含開(kāi)頭，不包含結(jié)尾
         * 3. 既不包含開(kāi)頭，也不包含結(jié)尾
         * 4. 既包含開(kāi)頭，也包含結(jié)尾
         */

        //包含結(jié)尾，不包含開(kāi)頭
        int p1 = process(str, left + 1, right);
        //包含開(kāi)頭，不包含結(jié)尾
        int p2 = process(str, left, right - 1);
        //既不包含開(kāi)頭，也不包含結(jié)尾
        int p3 = process(str, left + 1, right - 1);
        //既包含開(kāi)頭，也包含結(jié)尾
        int p4 = str[left] != str[right] ? 0 : (2 + process(str, left + 1, right - 1));
        //也可以改寫(xiě)成 int p4 = str[left] != str[right] ? 0 : (2 + p3);
        
        return Math.max(Math.max(p1, p2), Math.max(p3, p4));
    }


    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("a12b3c43def2ghi1kpm"));
    }
}

測(cè)試結(jié)果：?

算法27：最長(zhǎng)回文子序列長(zhǎng)度——范圍模型

分析過(guò)程

1. 假設(shè)字符串為 a12a21b，我們知道最長(zhǎng)回文子序列為12a21, 那么它的長(zhǎng)度就是5.

2. 構(gòu)建二維數(shù)組.? 行和列都是數(shù)組的下標(biāo)。遞歸的傳入?yún)?shù) 0 和??str.length() -1，分別代表數(shù)組的左邊開(kāi)始位置和右邊開(kāi)始位置。將left作為行，right作為列，那么可以推導(dǎo)出如下的表格信息

	0(a)	1(1)	2(2)	3(a)	4(2)	5(1)	6(b)
0(a)
1(1)	x
2(2)	x	x
3(a)	x	x	x
4(2)	x	x	x	x
5(1)	x	x	x	x	x
6(b)	x	x	x	x	x	x

3. 根據(jù)遞歸的

if (left == right) {
    return 1;
}

可以推算出對(duì)角線(xiàn)全部為 1.

	0(a)	1(1)	2(2)	3(a)	4(2)	5(1)	6(b)
0(a)	1
1(1)	x	1
2(2)	x	x	1
3(a)	x	x	x	1
4(2)	x	x	x	x	1
5(1)	x	x	x	x	x	1
6(b)	x	x	x	x	x	x	1

4. 根據(jù)遞歸

if (left == right -1) {
    return str[left] == str[right] ? 2 : 1;
}

可以推算出：

	0(a)	1(1)	2(2)	3(a)	4(2)	5(1)	6(b)
0(a)	1	1
1(1)	x	1	1
2(2)	x	x	1	1
3(a)	x	x	x	1	1
4(2)	x	x	x	x	1	1
5(1)	x	x	x	x	x	1	1
6(b)	x	x	x	x	x	x	1

5.? 核心推算過(guò)程

//包含結(jié)尾，不包含開(kāi)頭。我們知道（left，right）依賴(lài)（left+1, right）,即下一行
int p1 = process(str, left + 1, right);
//包含開(kāi)頭，不包含結(jié)尾. 我們知道（left，right）依賴(lài)（left, right -1）即前一列
int p2 = process(str, left, right - 1);
//既不包含開(kāi)頭，也不包含結(jié)尾。我們知道（left，right）依賴(lài)（left+1, right -1）即前一列的下一行
int p3 = process(str, left + 1, right - 1);
//既包含開(kāi)頭，也包含結(jié)尾。我們知道（left，right）依賴(lài)（left+1, right -1）即前一列的下一行
int p4 = str[left] != str[right] ? 0 : (2 + process(str, left + 1, right - 1));

也就是說(shuō)（left，right）依賴(lài)當(dāng)前行的前一列、下一行的當(dāng)前列和前一行的前一列/

也就是說(shuō)想要知道dp[4][6]的值，必須先知道dp[4][5]? dp[5][6] 和 dp[5][5] 的值。而這幾個(gè)值已經(jīng)推出來(lái)了，那就拿到最大值 1.

	0(a)	1(1)	2(2)	3(a)	4(2)	5(1)	6(b)
0(a)	1	1
1(1)	x	1	1
2(2)	x	x	1	1
3(a)	x	x	x	1	1
4(2)	x	x	x	x	1	1
5(1)	x	x	x	x	x	1	1
6(b)	x	x	x	x	x	x	1

?還是按照以上的信息，根據(jù)前一列、下一行的當(dāng)前列以及前一行的前一列可以推算出結(jié)果。

以dp[3][6]為例子。 dp[3][5]為3，?dp[4][6]為3，dp[4][5]為1. 并且字符串下標(biāo)3的值為a，6的位置為b， a!=b, 因此維持最大值3. 如果相等，那就額外再加 2。

? ? ? ? ? ? ? ? ? ? ????????????????? ? ????????依次類(lèi)推，第一個(gè)變化的位置為dp[2][4]

	0(a)	1(1)	2(2)	3(a)	4(2)	5(1)	6(b)
0(a)	1	1	1
1(1)	x	1	1	1
2(2)	x	x	1	1	3
3(a)	x	x	x	1	1	1
4(2)	x	x	x	x	1	1	1
5(1)	x	x	x	x	x	1	1
6(b)	x	x	x	x	x	x	1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 依次類(lèi)推，得到完整的表格信息

	0(a)	1(1)	2(2)	3(a)	4(2)	5(1)	6(b)
0(a)	1	1	1	3	3	5	5
1(1)	x	1	1	1	3	5	5
2(2)	x	x	1	1	3	3	3
3(a)	x	x	x	1	1	1	1
4(2)	x	x	x	x	1	1	1
5(1)	x	x	x	x	x	1	1
6(b)	x	x	x	x	x	x	1

動(dòng)態(tài)規(guī)劃版本

package code03.動(dòng)態(tài)規(guī)劃_07;

/**
 * 給定一個(gè)字符串str，返回這個(gè)字符串的最長(zhǎng)回文子序列長(zhǎng)度
 * 比如 ： str = “a12b3c43def2ghi1kpm”
 * 最長(zhǎng)回文子序列是“1234321”或者“123c321”，返回長(zhǎng)度7
 *
 * https://leetcode.com/problems/longest-palindromic-subsequence/
 */
public class PalindromeSubsequence_05_opt2
{
    public static int longestPalindromeSubseq(String str)
    {
        if (str == null || str.isEmpty()) {
            return 0;
        }

        //構(gòu)造一個(gè) n * n的矩陣
        char[] s = str.toCharArray();
        int[][] dp = new int[s.length][s.length];

        //最后一行的最后一列比較特殊，會(huì)出現(xiàn)數(shù)組越界，需要單獨(dú)設(shè)置
        dp[s.length-1][s.length-1] = 1;
        for (int i = 0; i < s.length - 1 ; i++) {
            //根據(jù)遞歸  if (left == right) 得到對(duì)角線(xiàn)全部為1
            dp[i][i] = 1;
            //根據(jù)遞歸 if (left == right -1) { 得到對(duì)角線(xiàn)的后一列值
            dp[i][i+1] = s[i] == s[i+1] ? 2 : 1;
        }

        //由于倒數(shù)第一、第二行已經(jīng)推算出來(lái)了，因此從倒數(shù)第三行開(kāi)始推算
        for (int row = s.length - 3; row >= 0; row--)
        {
            //從倒數(shù)第一行開(kāi)始推算。并且列需要隨著行變化而變化
            for (int col = row + 2; col < s.length ; col++)
            {
                //包含開(kāi)頭，不包含結(jié)尾
                int p1 = dp[row + 1][col];
                //包含結(jié)尾，不包含開(kāi)頭
                int p2 = dp[row][col - 1];
                //既不包含開(kāi)頭，也不包含結(jié)尾
                int p3 =  dp[row + 1][col - 1];
                //既包含開(kāi)頭，也包含結(jié)尾
                int p4 = s[row] != s[col] ? 0 : (2 + dp[row + 1][col - 1]);

                dp[row][col] = Math.max(Math.max(p1, p2), Math.max(p3, p4));
            }
        }

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



    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("a12b3c43def2ghi1kpm"));
    }
}

測(cè)試結(jié)果：

算法27：最長(zhǎng)回文子序列長(zhǎng)度——范圍模型

優(yōu)化動(dòng)態(tài)規(guī)劃：

	0(a)	1(1)	2(2)	3(a)	4(2)	5(1)	6(b)
0(a)	1	1	1
1(1)	x	1	1	1
2(2)	x	x	1	1	3
3(a)	x	x	x	1	1	1
4(2)	x	x	x	x	1	1	1
5(1)	x	x	x	x	x	1	1
6(b)	x	x	x	x	x	x	1

dp[2][4]位置是第一次發(fā)生變化的。下一輪，我們會(huì)推算出如下結(jié)果：

	0(a)	1(1)	2(2)	3(a)	4(2)	5(1)	6(b)
0(a)	1	1	1	3
1(1)	x	1	1	1	3
2(2)	x	x	1	1	3	3
3(a)	x	x	x	1	1	1	1
4(2)	x	x	x	x	1	1	1
5(1)	x	x	x	x	x	1	1
6(b)	x	x	x	x	x	x	1

而dp[1][5]位置依賴(lài) dp[1][4] 、 dp[2][5] 和 dp[2][4].?

但是dp[1][4] 和? [2][5]已經(jīng)推算出來(lái)了，他們都依賴(lài)dp[2][4]。

也就是說(shuō)dp[1][4] 和? [2][5]至少都是大于或等于dp[2][4位置的數(shù)據(jù)的，

我們的邏輯是獲取到最大值，既然能夠拿到大于等于它的值，那么dp[1][5]直接依賴(lài)dp[1][4] 和? [2][5]就可以了，沒(méi)必要再去依賴(lài)較小的dp[2][4]值了。

因此，單獨(dú)的依賴(lài)左下方，即p3就可以省略

遞歸優(yōu)化：

package code03.動(dòng)態(tài)規(guī)劃_07;

/**
 * 給定一個(gè)字符串str，返回這個(gè)字符串的最長(zhǎng)回文子序列長(zhǎng)度
 * 比如 ： str = “a12b3c43def2ghi1kpm”
 * 最長(zhǎng)回文子序列是“1234321”或者“123c321”，返回長(zhǎng)度7
 *
 * https://leetcode.com/problems/longest-palindromic-subsequence/
 */
public class PalindromeSubsequence_05_opt1
{
    public static int longestPalindromeSubseq(String str)
    {
        if (str == null || str.isEmpty()) {
            return 0;
        }

        return process(str.toCharArray(), 0, str.length() -1);
    }

    //范圍模型，需要討論樣本數(shù)據(jù)的開(kāi)頭和結(jié)尾
    public static int process(char[] str, int left, int right)
    {
        //如果長(zhǎng)度為1,也就是說(shuō)字符串只有一個(gè)字符
        if (left == right) {
            return 1;
        }

        //字符串只有2個(gè)元素. 如果第一個(gè)元素和第二個(gè)元素相同，則說(shuō)明回文
        //長(zhǎng)度為2. 否則，最長(zhǎng)子回文只有1，因?yàn)槲覀兡J(rèn)的子序列回文長(zhǎng)度就是為1.
        if (left == right -1) {
            return str[left] == str[right] ? 2 : 1;
        }

        /**
         * 最長(zhǎng)回文子序列, 有可能出現(xiàn)以下情況
         * 1. 包含結(jié)尾，不包含開(kāi)頭
         * 2. 包含開(kāi)頭，不包含結(jié)尾
         * 3. 既不包含開(kāi)頭，也不包含結(jié)尾
         * 4. 既包含開(kāi)頭，也包含結(jié)尾
         */

        //包含結(jié)尾，不包含開(kāi)頭
        int p1 = process(str, left + 1, right);
        //包含開(kāi)頭，不包含結(jié)尾
        int p2 = process(str, left, right - 1);
        //既不包含開(kāi)頭，也不包含結(jié)尾
        //int p3 = process(str, left + 1, right - 1);
        //既包含開(kāi)頭，也包含結(jié)尾
        int p4 = str[left] != str[right] ? 0 : (2 + process(str, left + 1, right - 1));

        return Math.max(Math.max(p1, p2), p4);
    }


    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("a12b3c43def2ghi1kpm"));
    }
}

動(dòng)態(tài)規(guī)劃版本優(yōu)化：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-468872.html

package code03.動(dòng)態(tài)規(guī)劃_07;

/**
 * 給定一個(gè)字符串str，返回這個(gè)字符串的最長(zhǎng)回文子序列長(zhǎng)度
 * 比如 ： str = “a12b3c43def2ghi1kpm”
 * 最長(zhǎng)回文子序列是“1234321”或者“123c321”，返回長(zhǎng)度7
 *
 * https://leetcode.com/problems/longest-palindromic-subsequence/
 */
public class PalindromeSubsequence_05_opt2
{
    public static int longestPalindromeSubseq(String str)
    {
        if (str == null || str.isEmpty()) {
            return 0;
        }

        //構(gòu)造一個(gè) n * n的矩陣
        char[] s = str.toCharArray();
        int[][] dp = new int[s.length][s.length];

        //最后一行的最后一列比較特殊，會(huì)出現(xiàn)數(shù)組越界，需要單獨(dú)設(shè)置
        dp[s.length-1][s.length-1] = 1;
        for (int i = 0; i < s.length - 1 ; i++) {
            //根據(jù)遞歸  if (left == right) 得到對(duì)角線(xiàn)全部為1
            dp[i][i] = 1;
            //根據(jù)遞歸 if (left == right -1) { 得到對(duì)角線(xiàn)的后一列值
            dp[i][i+1] = s[i] == s[i+1] ? 2 : 1;
        }

        //由于倒數(shù)第一、第二行已經(jīng)推算出來(lái)了，因此從倒數(shù)第三行開(kāi)始推算
        for (int row = s.length - 3; row >= 0; row--)
        {
            //從倒數(shù)第一行開(kāi)始推算。并且列需要隨著行變化而變化
            for (int col = row + 2; col < s.length ; col++)
            {
            /*    //包含開(kāi)頭，不包含結(jié)尾
                int p1 = dp[row + 1][col];
                //包含結(jié)尾，不包含開(kāi)頭
                int p2 = dp[row][col - 1];
                //既不包含開(kāi)頭，也不包含結(jié)尾
                int p3 =  dp[row + 1][col - 1];
                //既包含開(kāi)頭，也包含結(jié)尾
                int p4 = s[row] != s[col] ? 0 : (2 + dp[row + 1][col - 1]);

                dp[row][col] = Math.max(Math.max(p1, p2), Math.max(p3, p4));*/

                //包含開(kāi)頭，不包含結(jié)尾
                int p1 = dp[row + 1][col];
                //包含結(jié)尾，不包含開(kāi)頭
                int p2 = dp[row][col - 1];
                dp[row][col] = Math.max(p1, p2);

                if (s[row] == s[col] ) {
                    dp[row][col] = Math.max(dp[row][col], 2 + dp[row + 1][col - 1]);
                }
            }
        }
        return dp[0][s.length-1];
    }



    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("a12b3c43def2ghi1kpm"));
    }
}

到了這里，關(guān)于算法27：最長(zhǎng)回文子序列長(zhǎng)度——范圍模型的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！