# 0516. 最長回文子序列 ## 題目地址(516. 最長回文子序列) <https://leetcode-cn.com/problems/longest-palindromic-subsequence/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個字符串 s ，找到其中最長的回文子序列，并返回該序列的長度。可以假設 s 的最大長度為 1000 。 示例 1: 輸入: "bbbab" 輸出: 4 一個可能的最長回文子序列為 "bbbb"。 示例 2: 輸入: "cbbd" 輸出: 2 一個可能的最長回文子序列為 "bb"。 提示： 1 <= s.length <= 1000 s 只包含小寫英文字母 ``` ``` ## 前置知識 - 動態規劃 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這是一道最長回文的題目，要我們求出給定字符串的最大回文子序列。  解決這類問題的核心思想就是兩個字“延伸”，具體來說 - 如果一個字符串是回文串，那么在它左右分別加上一個相同的字符，那么它一定還是一個回文串，因此`回文長度增加2` - 如果一個字符串不是回文串，或者在回文串左右分別加不同的字符，得到的一定不是回文串,因此`回文長度不變，我們取[i][j-1]和[i+1][j]的較大值`  事實上，上面的分析已經建立了大問題和小問題之間的關聯， 基于此，我們可以建立動態規劃模型。 我們可以用 dp\[i\]\[j\] 表示 s 中從 i 到 j（包括 i 和 j）的回文序列長度， 狀態轉移方程只是將上面的描述轉化為代碼即可： ``` <pre class="calibre18">``` <span class="hljs-keyword">if</span> (s[i] === s[j]) { dp[i][j] = dp[i + <span class="hljs-params">1</span>][j - <span class="hljs-params">1</span>] + <span class="hljs-params">2</span>; } <span class="hljs-keyword">else</span> { dp[i][j] = <span class="hljs-params">Math</span>.max(dp[i][j - <span class="hljs-params">1</span>], dp[i + <span class="hljs-params">1</span>][j]); } ``` ``` base case 就是一個字符（軸對稱點是本身）  ## 關鍵點 - ”延伸“（extend） ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=516 lang=javascript * * [516] Longest Palindromic Subsequence */</span> <span class="hljs-title">/** * @param {string} s * @return {number} */</span> <span class="hljs-keyword">var</span> longestPalindromeSubseq = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">s</span>) </span>{ <span class="hljs-title">// bbbab 返回4</span> <span class="hljs-title">// tag : dp</span> <span class="hljs-keyword">const</span> dp = []; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = s.length - <span class="hljs-params">1</span>; i >= <span class="hljs-params">0</span>; i--) { dp[i] = <span class="hljs-params">Array</span>(s.length).fill(<span class="hljs-params">0</span>); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = i; j < s.length; j++) { <span class="hljs-keyword">if</span> (i - j === <span class="hljs-params">0</span>) dp[i][j] = <span class="hljs-params">1</span>; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (s[i] === s[j]) { dp[i][j] = dp[i + <span class="hljs-params">1</span>][j - <span class="hljs-params">1</span>] + <span class="hljs-params">2</span>; } <span class="hljs-keyword">else</span> { dp[i][j] = <span class="hljs-params">Math</span>.max(dp[i][j - <span class="hljs-params">1</span>], dp[i + <span class="hljs-params">1</span>][j]); } } } <span class="hljs-keyword">return</span> dp[<span class="hljs-params">0</span>][s.length - <span class="hljs-params">1</span>]; }; ``` ``` **復雜度分析** - 時間復雜度：O(N2)O(N^2)O(N2) - 空間復雜度：O(N2)O(N^2)O(N2) ## 相關題目 - [5.longest-palindromic-substring](5.longest-palindromic-substring.html) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。