<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 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 只包含小寫英文字母 ``` ``` ## 前置知識 - 動態規劃 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這是一道最長回文的題目,要我們求出給定字符串的最大回文子序列。 ![](https://img.kancloud.cn/a7/57/a757c3fc333b1fca01e9a307c51bb0d3_482x228.jpg) 解決這類問題的核心思想就是兩個字“延伸”,具體來說 - 如果一個字符串是回文串,那么在它左右分別加上一個相同的字符,那么它一定還是一個回文串,因此`回文長度增加2` - 如果一個字符串不是回文串,或者在回文串左右分別加不同的字符,得到的一定不是回文串,因此`回文長度不變,我們取[i][j-1]和[i+1][j]的較大值` ![](https://img.kancloud.cn/b6/02/b602ae9bea452f998aa0dc47b2ccdaf3_515x341.jpg) 事實上,上面的分析已經建立了大問題和小問題之間的關聯, 基于此,我們可以建立動態規劃模型。 我們可以用 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 就是一個字符(軸對稱點是本身) ![](https://img.kancloud.cn/38/77/3877e115a9c5c1d9be91ee6c909b24c3_416x181.jpg) ## 關鍵點 - ”延伸“(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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看