{"id":2792,"date":"2022-04-17T15:21:28","date_gmt":"2022-04-17T07:21:28","guid":{"rendered":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2792"},"modified":"2022-04-17T15:51:46","modified_gmt":"2022-04-17T07:51:46","slug":"dp%e7%ac%ac17%e5%a4%a9","status":"publish","type":"post","link":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2792","title":{"rendered":"dp\u7b2c17\u5929"},"content":{"rendered":"\n

5. \u6700\u957f\u56de\u6587\u5b50\u4e32<\/a><\/p>\n\n\n\n

\u8fd9\u9898\uff0c\u8fd8\u662f\u4e0d\u641edp\u4e86\uff0c\u7528\u4e2d\u5fc3\u6269\u6563\u6cd5\u6765\u5904\u7406\uff0c\u6269\u6563\u4e24\u6b21\uff0c\u4e00\u6b21\u5f53\u4f5c\u5947\u6570\uff0c\u4e00\u6b21\u5f53\u4f5c\u5076\u6570\uff0c\u770b\u54ea\u4e2a\u5f97\u5230\u7684\u7ed3\u679c\u66f4\u5927\uff0c\u66f4\u65b0\u4e4b\u524d\u7684start\u548cmaxLen;<\/p>\n\n\n\n

len = right – left – 1;<\/p>\n\n\n\n

start = i – (len-1)\/2 (\u7efc\u5408\u4e86\u5947\u6570\u5076\u6570\u7684\u7ed3\u679c)<\/p>\n\n\n\n


\/**
<\/em> *
<\/em> 5. \u6700\u957f\u56de\u6587\u5b50\u4e32
<\/em> \u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32 s\uff0c\u627e\u5230 s \u4e2d\u6700\u957f\u7684\u56de\u6587\u5b50\u4e32\u3002
<\/em>
<\/em>
<\/em>
<\/em> \u793a\u4f8b 1\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1as = \"babad\"
<\/em> \u8f93\u51fa\uff1a\"bab\"
<\/em> \u89e3\u91ca\uff1a\"aba\" \u540c\u6837\u662f\u7b26\u5408\u9898\u610f\u7684\u7b54\u6848\u3002
<\/em> \u793a\u4f8b 2\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1as = \"cbbd\"
<\/em> \u8f93\u51fa\uff1a\"bb\"
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> 1 <= s.length <= 1000
<\/em> s \u4ec5\u7531\u6570\u5b57\u548c\u82f1\u6587\u5b57\u6bcd\u7ec4\u6210
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>public class Question5 {

   public static String longestPalindrome(String s) {
      int start = 0;
      int maxLen = 0;

      for(int i=0; i<s.length(); i++){
         int len1 = expandAroundCenter<\/em>(s, i, i);
         int len2 = expandAroundCenter<\/em>(s, i, i+1);
         int len = Math.max<\/em>(len1, len2);
         if(len > maxLen){
            start = i - (len-1) \/ 2 ;
            maxLen = len;
         }
      }

      return s.substring(start, start + maxLen);
   }


   public static int expandAroundCenter(String s, int left, int right) {
      while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
         --left;
         ++right;
      }
      \/\/ \u8df3\u51fa\u5faa\u73af\uff0cs.charAt(left) != s.charAt(right)\uff0c\u6240\u4ee5\u5f97\u5230len = right - left - 1;
      return right - left - 1;
   }

   public static void main(String args[]){
\/\/    System.out.println(lengthOfLongestSubstring(\"abcabcbb\"));
\/\/    System.out.println(lengthOfLongestSubstring(\"bbbbb\"));
\/\/    System.out.println(lengthOfLongestSubstring(\"pwwkew\"));
\/\/    System.out.println(lengthOfLongestSubstring(\"dvdf\"));
   }
}<\/pre>\n\n\n\n
516. \u6700\u957f\u56de\u6587\u5b50\u5e8f\u5217<\/a><\/p>\n\n\n\n
\/\/ \u8fd9\u9898\u8981\u6ce8\u610f\u7684\u5c31\u662f\u5b50\u5e8f\u5217\u548c\u5b57\u4e32\u7684\u533a\u522b\n\n\/\/ \u5982\u679ci,j\u5bf9\u5e94\u7684char\u76f8\u540c\uff0cdp[i][j] = dp[i+1][j-1] + 2;\n\/\/ \u5982\u679ci,j\u5bf9\u5e94\u7684char\u4e0d\u76f8\u540c\uff0cdp[i][j] = max(dp[i+1][j],dp[i][j-1]);\n<\/pre>\n\n\n\n

\/**
<\/em> *
<\/em> 516. \u6700\u957f\u56de\u6587\u5b50\u5e8f\u5217
<\/em> \u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32 s \uff0c\u627e\u51fa\u5176\u4e2d\u6700\u957f\u7684\u56de\u6587\u5b50\u5e8f\u5217\uff0c\u5e76\u8fd4\u56de\u8be5\u5e8f\u5217\u7684\u957f\u5ea6\u3002
<\/em>
<\/em> \u5b50\u5e8f\u5217\u5b9a\u4e49\u4e3a\uff1a\u4e0d\u6539\u53d8\u5269\u4f59\u5b57\u7b26\u987a\u5e8f\u7684\u60c5\u51b5\u4e0b\uff0c\u5220\u9664\u67d0\u4e9b\u5b57\u7b26\u6216\u8005\u4e0d\u5220\u9664\u4efb\u4f55\u5b57\u7b26\u5f62\u6210\u7684\u4e00\u4e2a\u5e8f\u5217\u3002
<\/em>
<\/em>
<\/em>
<\/em> \u793a\u4f8b 1\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1as = \"bbbab\"
<\/em> \u8f93\u51fa\uff1a4
<\/em> \u89e3\u91ca\uff1a\u4e00\u4e2a\u53ef\u80fd\u7684\u6700\u957f\u56de\u6587\u5b50\u5e8f\u5217\u4e3a \"bbbb\" \u3002
<\/em> \u793a\u4f8b 2\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1as = \"cbbd\"
<\/em> \u8f93\u51fa\uff1a2
<\/em> \u89e3\u91ca\uff1a\u4e00\u4e2a\u53ef\u80fd\u7684\u6700\u957f\u56de\u6587\u5b50\u5e8f\u5217\u4e3a \"bb\" \u3002
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> 1 <= s.length <= 1000
<\/em> s \u4ec5\u7531\u5c0f\u5199\u82f1\u6587\u5b57\u6bcd\u7ec4\u6210
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>public class Question516 {

   public int longestPalindromeSubseq(String s) {

      \/\/ \u8fd9\u9898\u8981\u6ce8\u610f\u7684\u5c31\u662f\u5b50\u5e8f\u5217\u548c\u5b57\u4e32\u7684\u533a\u522b

      \/\/ \u5982\u679ci,j\u5bf9\u5e94\u7684char\u76f8\u540c\uff0cdp[i][j] = dp[i+1][j-1] + 2;
      \/\/ \u5982\u679ci,j\u5bf9\u5e94\u7684char\u4e0d\u76f8\u540c\uff0cdp[i][j] = max(dp[i+1][j],dp[i][j-1]);


      int len = s.length();
      int[][] dp = new int[len+1][len+1]; \/\/ dp[i][j] = dp[i+1][j-1] + 2;  \u957f\u5ea6\u591a+1

      for(int i = len - 1; i>=0; i--){
         dp[i][i] = 1;
         char ci = s.charAt(i);
         for(int j = i + 1; j<len; j++){
            char cj = s.charAt(j);
            if(ci == cj){
               dp[i][j] = dp[i+1][j-1] + 2;
            }else {
               dp[i][j] = Math.max<\/em>(dp[i+1][j], dp[i][j-1]);
            }
         }
      }


      return dp[0][len-1];
   }

   public static void main(String args[]){
   }
}<\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
5. \u6700\u957f\u56de\u6587\u5b50\u4e32 \u8fd9\u9898\uff0c\u8fd8\u662f\u4e0d\u641edp\u4e86\uff0c\u7528\u4e2d\u5fc3\u6269\u6563\u6cd5\u6765\u5904\u7406\uff0c\u6269\u6563\u4e24\u6b21\uff0c\u4e00\u6b21\u5f53\u4f5c\u5947\u6570\uff0c\u4e00\u6b21\u5f53\u4f5c\u5076\u6570\uff0c\u770b\u54ea\u4e2a\u5f97\u5230 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[155],"tags":[198],"_links":{"self":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2792"}],"collection":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2792"}],"version-history":[{"count":10,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2792\/revisions"}],"predecessor-version":[{"id":2802,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2792\/revisions\/2802"}],"wp:attachment":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2792"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2792"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2792"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}