參考這里：示例: [a, b , c, d , e]

解答這類題目, 省略不掉遍歷, 因此我們先從遍歷方式說起，通常我們遍歷子串或者子序列有三種遍歷方式

• 以某個(gè)節(jié)點(diǎn)為開頭的所有子序列: 如 [a]，[a, b]，[ a, b, c] ... 再?gòu)囊?b 為開頭的子序列開始遍歷 [b] [b, c]。即暴力解法奶浦。

• 根據(jù)子序列的長(zhǎng)度為標(biāo)桿，如先遍歷出子序列長(zhǎng)度為 1 的子序列，在遍歷出長(zhǎng)度為 2 的 等等酿秸。 leetcode (5. 最長(zhǎng)回文子串 ) 中的解法就用到了。

• 以子序列的結(jié)束節(jié)點(diǎn)為基準(zhǔn)魏烫，先遍歷出以某個(gè)節(jié)點(diǎn)為結(jié)束的所有子序列辣苏，因?yàn)槊總€(gè)節(jié)點(diǎn)都可能會(huì)是子序列的結(jié)束節(jié)點(diǎn)，因此要遍歷下整個(gè)序列哄褒，如: 以 b 為結(jié)束點(diǎn)的所有子序列: [a , b] [b] 以 c 為結(jié)束點(diǎn)的所有子序列: [a, b, c] [b, c] [ c ]稀蟋。這里因?yàn)榭梢援a(chǎn)生遞推關(guān)系, 采用動(dòng)態(tài)規(guī)劃時(shí), 經(jīng)常通過此種遍歷方式, 如 背包問題, 最大公共子串

====================== 子序問題（連續(xù)）======================

1.最大子序和（53 - 易）

題目描述：給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）呐赡，返回其最大和退客。與劍指42相同。

示例 :

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 萌狂。

思路：典型的動(dòng)態(tài)規(guī)劃档玻，關(guān)鍵點(diǎn)：

• dp[i]：以nums[i]為結(jié)尾的最大和的連續(xù)子數(shù)組（重要）
• 狀態(tài)轉(zhuǎn)移方程：dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])，因?yàn)樵乜赡艽嬖谪?fù)數(shù)粥脚。

由于dp[i]只依賴dp[i - 1]窃肠，所以可以用一個(gè)變量pre記錄狀態(tài)更替。

代碼實(shí)現(xiàn)：

class Solution {
    // 動(dòng)態(tài)規(guī)劃(注意：最后返回的是所有位置中最大的)
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (nums == null || n == 0) {
            return 0;
        }
        // dp[i]:以i結(jié)尾的最大子序和
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ans = nums[0];

        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    // 狀態(tài)壓縮
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (nums == null || n == 0) {
            return 0;
        }
        int pre = nums[0];
        int ans = nums[0];

        for (int i = 1; i < n; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            ans = Math.max(ans, pre);
        } 
        return ans;
    }
}

2.最長(zhǎng)連續(xù)遞增序列（674 - 易）

題目描述：給定一個(gè)未經(jīng)排序的整數(shù)數(shù)組刷允，找到最長(zhǎng)且 連續(xù)遞增的子序列冤留，并返回該序列的長(zhǎng)度。

連續(xù)遞增的子序列 可以由兩個(gè)下標(biāo) l 和 r（l < r）確定树灶，如果對(duì)于每個(gè) l <= i < r纤怒，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是連續(xù)遞增子序列天通。

示例 :

輸入：nums = [1,3,5,4,7]
輸出：3
解釋：最長(zhǎng)連續(xù)遞增序列是 [1,3,5], 長(zhǎng)度為3泊窘。
盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續(xù)的，因?yàn)?5 和 7 在原數(shù)組里被 4 隔開像寒。 

思路：典型的動(dòng)態(tài)規(guī)劃：

• dp[i]：以nums[i]為結(jié)尾的最長(zhǎng)連續(xù)遞增序列的長(zhǎng)度
• 狀態(tài)轉(zhuǎn)移方程：如果遞增：dp[i] = dp[i - 1] + 1烘豹，否則dp[i] = 1。

由于dp[i]只依賴dp[i - 1]诺祸，所以可以用一個(gè)變量pre記錄狀態(tài)更替携悯。

代碼實(shí)現(xiàn)：

class Solution {
    // 動(dòng)態(tài)規(guī)劃（最后返回整個(gè)數(shù)組中最長(zhǎng)的連續(xù)遞增子序列）
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        if (nums == null || n == 0) {
            return 0;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        int ans = 1;

        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 1;
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    // 狀態(tài)壓縮
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        if (nums == null || n == 0) {
            return 0;
        }
        int pre = 1;
        int ans = 1;

        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                pre = pre + 1;
            } else {
                pre = 1;
            }
            ans = Math.max(ans, pre);
        }
        return ans;
    }
}

3.最長(zhǎng)重復(fù)子數(shù)組（718 - 中）

題目描述：給兩個(gè)整數(shù)數(shù)組 A 和 B ，返回兩個(gè)數(shù)組中公共的筷笨、長(zhǎng)度最長(zhǎng)的子數(shù)組的長(zhǎng)度憔鬼。

示例 :

輸入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
輸出：3
解釋：
長(zhǎng)度最長(zhǎng)的公共子數(shù)組是 [3, 2, 1] 。

思路：典型的動(dòng)態(tài)規(guī)劃：

• dp[i][j]：以nums1[i]和nums2[j]為結(jié)尾的最長(zhǎng)公共子數(shù)組胃夏。
• 狀態(tài)轉(zhuǎn)移方程：相等：dp[i][j] = dp[i - 1][j - 1] + 1轴或，否則dp[i][j] = 0。（即以nums1[i] 和 nums2[j] 結(jié)尾的公共子數(shù)組為0仰禀！因?yàn)橐筮B續(xù)Ｕ昭恪）

ps：為了簡(jiǎn)化代碼，我們判斷條件是nums[i - 1]和nums[j - 1]答恶！

空間壓縮：逆序遍歷囊榜，保證不覆蓋。

代碼實(shí)現(xiàn)：

class Solution {
    // 動(dòng)態(tài)規(guī)劃
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0 || n == 0) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];
        int ans = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }

    // 空間壓縮：dp[i][j]只依賴dp[i - 1][j - 1]亥宿，這里壓縮到一列！
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0 || n == 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        int ans = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = n; j >= 1; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                } else {
                    dp[j] = 0;
                }
                ans = Math.max(ans, dp[j]);
            }
        }
        return ans;
    }
}

====================== 子序問題（不連續(xù)）=====================

1.最長(zhǎng)公共子序列（1143 - 中）

題目描述：給定兩個(gè)字符串 text1 和 text2砂沛，返回這兩個(gè)字符串的最長(zhǎng) 公共子序列 的長(zhǎng)度烫扼。如果不存在 公共子序列 ，返回 0 碍庵。

一個(gè)字符串的 子序列 是指這樣一個(gè)新的字符串：它是由原字符串在不改變字符的相對(duì)順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串映企。

例如悟狱，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列堰氓。
兩個(gè)字符串的 公共子序列 是這兩個(gè)字符串所共同擁有的子序列挤渐。

示例 :

輸入：text1 = "abcde", text2 = "ace" 
輸出：3  
解釋：最長(zhǎng)公共子序列是 "ace" ，它的長(zhǎng)度為 3 双絮。

思路：典型動(dòng)態(tài)規(guī)劃浴麻，類比T718，但這里是是不連續(xù)的：

• 當(dāng)前兩個(gè)字符囤攀，我們可以利用之前的結(jié)果
• 故软免，最終結(jié)果不需要遍歷整個(gè)數(shù)組，最后一個(gè)就是全局最大焚挠。

代碼實(shí)現(xiàn)：

class Solution {
    // 動(dòng)態(tài)規(guī)劃
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[m][n];
    }
}

2.最長(zhǎng)遞增子序列（300 - 中）

題目描述：給你一個(gè)整數(shù)數(shù)組 nums 膏萧，找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度。

子序列是由數(shù)組派生而來的序列蝌衔，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序榛泛。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列噩斟。

示例 :

輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長(zhǎng)遞增子序列是 [2,3,7,101]曹锨，因此長(zhǎng)度為 4 。

思路：基本解法是動(dòng)態(tài)規(guī)劃亩冬，對(duì)比T674（連續(xù)）艘希，不同點(diǎn)：

• 由于不連續(xù)，當(dāng)前位置依賴依賴1~i-1位置的值（不能壓縮空間）
• 當(dāng)出現(xiàn)不遞增時(shí)硅急，我們不做操作覆享，只有遞增才遍歷更新最大值。
• dp數(shù)組所有元素初始化為1（初始最長(zhǎng)遞增子序列是其本身）营袜。

另外本題最優(yōu)解：貪心+二分撒顿。思路比較巧妙，新建數(shù)組 cell荚板，用于保存最長(zhǎng)上升子序列凤壁。對(duì)原序列進(jìn)行遍歷，將每位元素二分插入 cell 中跪另，（注意cell數(shù)組嚴(yán)格上升拧抖，故可以使用二分查找）。

• 如果插入元素大于cell數(shù)組中的最大值免绿，直接加在后邊唧席；
• 否則，用它覆蓋掉cell數(shù)組中比它大的元素中最小的那個(gè)（因?yàn)橐呀?jīng)有序所以可以使用二分查找）。比如：cell中已經(jīng)有[1, 3, 5]淌哟，插入2迹卢，則覆蓋3，cell數(shù)組變?yōu)閇1, 2, 5]

總之徒仓，思想就是讓 cell 中存儲(chǔ)比較小的元素腐碱。重要，cell 未必是真實(shí)的最長(zhǎng)上升子序列掉弛，但長(zhǎng)度是對(duì)的!

代碼實(shí)現(xiàn)：

 class Solution {
    // 動(dòng)態(tài)規(guī)劃
     public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n <= 1) return n;
        // dp[i]：以i結(jié)尾的最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        int ans = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 注意：不能進(jìn)行空間壓縮症见，因?yàn)楫?dāng)前位置i依賴1~i-1位置的值
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n <= 1) return n;
        // cell存儲(chǔ)比較小的元素
        int[] cell = new int[n];
        cell[0] = nums[0];
        // index記錄最長(zhǎng)連續(xù)遞增子序列的結(jié)束索引
        int index = 0;
        for (int i = 1; i < n; i++) {
            int l = 0, r = index;
            if (nums[i] > cell[index]) {
                index++;
                cell[index] = nums[i];
            } else {
                while (l < r) {
                    int mid = l + ((r - l) >> 1);
                    if (nums[i] > cell[mid]) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                cell[l] = nums[i];
            }      
        }
        return index + 1;
    }
}

3.不相交的線（1035 - 中）

題目描述：在兩條獨(dú)立的水平線上按給定的順序?qū)懴?nums1 和 nums2 中的整數(shù)。

現(xiàn)在狰晚，可以繪制一些連接兩個(gè)數(shù)字 nums1[i] 和 nums2[j] 的直線筒饰，這些直線需要同時(shí)滿足滿足：

nums1[i] == nums2[j]
且繪制的直線不與任何其他連線（非水平線）相交。
請(qǐng)注意壁晒，連線即使在端點(diǎn)也不能相交：每個(gè)數(shù)字只能屬于一條連線瓷们。

以這種方法繪制線條，并返回可以繪制的最大連線數(shù)秒咐。

示例 :

輸入：nums1 = [1,4,2], nums2 = [1,2,4]
輸出：2
解釋：可以畫出兩條不交叉的線谬晕，如上圖所示。 
但無法畫出第三條不相交的直線携取，因?yàn)閺?nums1[1]=4 到 nums2[2]=4 的直線將與從 nums1[2]=2 到 nums2[1]=2 的直線相交攒钳。

思路：本題本質(zhì)就是求最長(zhǎng)公共子序列，與1143相同雷滋。代碼相同不撑，空間壓縮省略。

代碼實(shí)現(xiàn)：

class Solution {
    // 動(dòng)態(tài)規(guī)劃
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0 || n == 0) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

===================== 子序問題（編輯距離）=====================

1.不同的子序列（115 - 難）

題目描述：給定一個(gè)字符串 s 和一個(gè)字符串 t 晤斩，計(jì)算在 s 的子序列中 t 出現(xiàn)的個(gè)數(shù)焕檬。

字符串的一個(gè) 子序列 是指，通過刪除一些（也可以不刪除）字符且不干擾剩余字符相對(duì)位置所組成的新字符串澳泵。（例如实愚，"ACE" 是 "ABCDE" 的一個(gè)子序列，而 "AEC" 不是）

題目數(shù)據(jù)保證答案符合 32 位帶符號(hào)整數(shù)范圍兔辅。

示例 :

輸入：s = "rabbbit", t = "rabbit"
輸出：3
解釋：
如下圖所示, 有 3 種可以從 s 中得到 "rabbit" 的方案腊敲。
(上箭頭符號(hào) ^ 表示選取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

思路：本題是一個(gè)字符串匹配問題，即在主串s中找模式串t维苔，要求：尋找s子序列中為t的個(gè)數(shù)（t是s的子序列）碰辅。典型動(dòng)態(tài)規(guī)劃，關(guān)鍵點(diǎn)：

• dp[i][j] 代表 T 前 i 字符串可以由 S 前j 字符串組成最多個(gè)數(shù)介时。
• 狀態(tài)轉(zhuǎn)移方程：注：當(dāng)s[j] == t[i]是乎赴，這里的j位置可選也可以不選忍法。即主串中的j的位置。
  • 當(dāng)S[j] == T[i] , dp[i][j] = dp[i-1][j-1] + dp[i][j-1];即只有相等榕吼，模式串才移動(dòng)。
  • 當(dāng) S[j] != T[i] , dp[i][j] = dp[i][j-1]

注意：dp數(shù)組開辟長(zhǎng)度勉失，因?yàn)閟和t的子序列還有空字符串存在羹蚣。

代碼實(shí)現(xiàn)：

public int numDistinct(String s, String t) {
    int sl = s.length(), tl = t.length();
    int[][] dp = new int[tl + 1][sl + 1];
    // t字符串為空，空串是所有字符串的子集
    for (int j = 0; j <= sl; j++) dp[0][j] = 1;

    for (int i = 1; i <= tl; i++) {
        for (int j = 1; j <= sl; j++) {
            if (t.charAt(i - 1) == s.charAt(j - 1)) 
                // j位置選或者不選（輸出所有的可能所以是+）
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
            else 
                dp[i][j] = dp[i][j - 1];
        }
    }
    return dp[tl][sl];
}

2.判斷子序列（392 - 易）

題目描述：給定字符串 s 和 t 乱凿，判斷 s 是否為 t 的子序列顽素。

字符串的一個(gè)子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對(duì)位置形成的新字符串。（例如徒蟆，"ace"是"abcde"的一個(gè)子序列胁出，而"aec"不是）。

進(jìn)階：

如果有大量輸入的 S兆蕉，稱作 S1, S2, ... , Sk 其中 k >= 10億嫁盲，你需要依次檢查它們是否為 T 的子序列雀监。在這種情況下，你會(huì)怎樣改變代碼抑淫？

示例 :

輸入：s = "abc", t = "ahbgdc"
輸出：true

思路：本題動(dòng)態(tài)規(guī)劃比上題簡(jiǎn)單。

• 本題可以直接根據(jù)字符串的String.indexOf（char ch, int index）：查找字符在字符串中從指定位置開始第一次出現(xiàn)的索引姥闪，沒有則返回-1始苇。
• 也可以使用雙指針進(jìn)行比較，實(shí)現(xiàn)比較簡(jiǎn)單（推薦？鹪）催式。
• 動(dòng)態(tài)規(guī)劃（效率較低）：字符串匹配問題，關(guān)鍵點(diǎn)：
  • dp[i][j]：s 的前 i 個(gè)字符與 t的前 j 個(gè)字符中公共子序列的長(zhǎng)度（匹配的長(zhǎng)度）
  • 狀態(tài)轉(zhuǎn)移方程：如果字符相同dp[i][j] = dp[i - 1][j - 1] + 1避归，否則dp[i][j] = dp[i][j - 1]荣月。ps：這里是判斷 s 是否為 t 的子序列，當(dāng)最后公共子序列長(zhǎng)度 = m（s的長(zhǎng)度）槐脏，說明是子序列喉童。

代碼實(shí)現(xiàn)：

class Solution {

    // 庫(kù)函數(shù)：判斷索引是否存在
    public boolean isSubsequence(String s, String t) {
        int index = -1;
        for (char ch : s.toCharArray()) {
            index = t.indexOf(ch, index + 1); 
            if (index == -1) {
                return false;
            }
        }
        return true;
    }

    // 雙指針
    public boolean isSubsequence(String s, String t) {
        int m = s.length(), n = t.length();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == m;
    }
    
    // 動(dòng)態(tài)規(guī)劃
    public boolean isSubsequence(String s, String t) {
        int m = s.length(), n = t.length();
        // dp[i][j]：s的前i個(gè)字符是否與t的前j個(gè)字符公共子序列的長(zhǎng)度（匹配的長(zhǎng)度）
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[m][n] == m ? true : false;
    }
}

待補(bǔ)充。顿天。583堂氯， 72

===================== 子序問題（回文）=====================

1.最長(zhǎng)回文子序列（516 - 中）

題目描述：給定一個(gè)字符串 s ，找到其中最長(zhǎng)的回文子序列牌废，并返回該序列的長(zhǎng)度咽白。可以假設(shè) s 的最大長(zhǎng)度為 1000 鸟缕。

示例 :

輸入:"bbbab"
輸出:4
一個(gè)可能的最長(zhǎng)回文子序列為 "bbbb"晶框。

思路：本題目標(biāo)是返回最長(zhǎng)的回文子序列的長(zhǎng)度排抬，使用動(dòng)態(tài)規(guī)劃：

• dp數(shù)組：在子串 s[i..j] 中，最長(zhǎng)回文子序列的長(zhǎng)度為 dp[i][j]授段，最終目標(biāo)是 dp[0][n - 1]蹲蒲。
• 狀態(tài)轉(zhuǎn)移方程比較簡(jiǎn)單，相同添加（長(zhǎng)度+2）侵贵，不同選兩個(gè)邊界加與不加的最大值届搁。

if (s[i] == s[j])
    // 它倆一定在最長(zhǎng)回文子序列中
    dp[i][j] = dp[i + 1][j - 1] + 2;
else
    // s[i+1..j] 和 s[i..j-1] 誰(shuí)的回文子序列更長(zhǎng)？
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

需要注意的是：根據(jù)一般位置的依賴關(guān)系（每個(gè)元素可能依賴左/下/左下元素）窍育，我們需要從左下角向右上角填元素卡睦。只需要從對(duì)角線開始（右上部分，即i <= j）漱抓。

代碼實(shí)現(xiàn)：

class Solution {
    
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (cs[i] == cs[j]) {
                    // 相等直接加入
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

2.最長(zhǎng)回文子串（5 - 中）

題目描述：給你一個(gè)字符串 s表锻，找到 s 中最長(zhǎng)的回文子串。

示例 :

輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案乞娄。

思路：本題比較容易想到的是中心擴(kuò)散法：從每個(gè)位置向兩邊擴(kuò)散瞬逊，遇到不是回文的停止擴(kuò)散。記錄最長(zhǎng)的回文子串.

• 要分奇數(shù)中心擴(kuò)散和偶數(shù)中心擴(kuò)散兩種情況（取最大值）补胚。
• 當(dāng)上述最大值大于當(dāng)前最長(zhǎng)回文子串码耐，更新最長(zhǎng)會(huì)子串開始和結(jié)束位置。
• 遍歷每個(gè)位置溶其，然后擴(kuò)散骚腥，時(shí)間復(fù)雜度O(N^2)。

顯然上述會(huì)有大量的重復(fù)計(jì)算瓶逃，可以使用動(dòng)態(tài)規(guī)劃進(jìn)行優(yōu)化：

• dp[i][j] 表示：子串 s[i..j] 是否為回文子串束铭，這里子串 s[i..j] 定義為左閉右閉區(qū)間，即可以取到 s[i] 和 s[j]厢绝。
• 根據(jù)頭尾字符是否相等契沫，需要分類討論：
  dp[i][j] = (s[i] == s[j]) and (dp[i + 1][j - 1] or j - i < 3)，包含奇偶情況昔汉。

代碼實(shí)現(xiàn)：

class Solution {
    
    // 中心擴(kuò)展法 
    public String longestPalindrome(String s) {
        char[] cs = s.toCharArray();
        int len = cs.length;
        if (len < 2) {
            return s;
        }

        int start = 0;
        int end = 0;
        for (int i = 0; i < len; i++) {
            int len1 = extendSubString(cs, i, i);
            int len2 = extendSubString(cs, i, i + 1);

            int max = Math.max(len1, len2);
            if (max > end - start) {
                // 對(duì)于（如a b b a）懈万，i代表左b位置
                start = i - (max - 1) / 2;
                end = i + max / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int extendSubString(char[] cs, int left, int right) {
        while (left >= 0 && right < cs.length && cs[left] == cs[right]) {
            left--;
            right++;
        }
        // right - left + 1 - 2
        return right - left - 1;
    }

    // 動(dòng)態(tài)規(guī)劃
    public String longestPalindrome(String s) {
        char[] cs = s.toCharArray();
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int start = 0;
        int end = 0;
        int maxLen = 0;

        for (int j = 0; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (cs[i] == cs[j] && (dp[i + 1][j - 1] || j - i < 3)) {
                    dp[i][j] = true;
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        start = i;
                        end = j;
                    }
                }
            }
        }
        return s.substring(start, end + 1);
    }
}