{"id":893,"date":"2020-03-31T21:26:32","date_gmt":"2020-04-01T04:26:32","guid":{"rendered":"http:\/\/209.126.2.187\/?p=893"},"modified":"2020-04-15T21:38:41","modified_gmt":"2020-04-16T04:38:41","slug":"palindrome","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/03\/31\/palindrome\/","title":{"rendered":"Palindrome &#038; DP"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Summary <\/h2>\n\n\n\n<p>In this post, I will introduce some problems related to palindrome and dynamic programming. <\/p>\n\n\n\n<p>A palindrome has a property that, if we add two equal characters in both side of it, it is still a palindrome. <\/p>\n\n\n\n<h2 class=\"wp-block-heading\">OJ<\/h2>\n\n\n\n\n<table id=\"tablepress-4\" class=\"tablepress tablepress-id-4\">\n<thead>\n<tr class=\"row-1\">\n\t<td class=\"column-1\"><\/td><th class=\"column-2\">Trick<\/th><th class=\"column-3\">Difficulty<\/th>\n<\/tr>\n<\/thead>\n<tbody class=\"row-striping row-hover\">\n<tr class=\"row-2\">\n\t<td class=\"column-1\"><a href=\"https:\/\/leetcode.com\/problems\/palindrome-partitioning-iii\/\" rel=\"noopener noreferrer\" target=\"_blank\">LC 1278. Palindrome Partitioning III<\/a><\/td><td class=\"column-2\">Cost to Make Palindrome + DP<\/td><td class=\"column-3\">6-7 points<\/td>\n<\/tr>\n<tr class=\"row-3\">\n\t<td class=\"column-1\"><a href=\"https:\/\/leetcode.com\/problems\/palindrome-partitioning-ii\/\" rel=\"noopener noreferrer\" target=\"_blank\">LC 132. Palindrome Partitioning II<\/a><\/td><td class=\"column-2\">Is Palindrome + DP<\/td><td class=\"column-3\">5 points<\/td>\n<\/tr>\n<tr class=\"row-4\">\n\t<td class=\"column-1\"><a href=\"https:\/\/leetcode.com\/problems\/count-different-palindromic-subsequences\/solution\/\" rel=\"noopener noreferrer\" target=\"_blank\">LC 730. Count Different Palindromic Subsequences <\/a><\/td><td class=\"column-2\">3D DP<\/td><td class=\"column-3\">7 points<\/td>\n<\/tr>\n<tr class=\"row-5\">\n\t<td class=\"column-1\"><a href=\"https:\/\/leetcode.com\/problems\/palindrome-removal\/\" rel=\"noopener noreferrer\" target=\"_blank\">LC 1246. Palindrome Removal<\/a><\/td><td class=\"column-2\">DP + \"A...A\" is still a Palindrome<\/td><td class=\"column-3\">6-7 points<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<!-- #tablepress-4 from cache -->\n\n\n\n<h2 class=\"wp-block-heading\">Details<\/h2>\n\n\n\n<h4 class=\"wp-block-heading\"><a rel=\"noreferrer noopener\" href=\"https:\/\/leetcode.com\/problems\/palindrome-partitioning-iii\/\" target=\"_blank\">LC 1278<\/a> Palindrome Partitioning III<\/h4>\n\n\n\n<p>Difficulty: 6-7 points<\/p>\n\n\n\n<p>Given a string&nbsp;<code>s<\/code>&nbsp;containing lowercase letters and an integer&nbsp;<code>k<\/code>. You could,<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>First, change some characters of&nbsp;<code>s<\/code>&nbsp;to other lowercase English letters.<\/li><li>Then divide&nbsp;<code>s<\/code>&nbsp;into&nbsp;<code>k<\/code>&nbsp;non-empty disjoint substrings such that each substring is palindrome.<\/li><\/ul>\n\n\n\n<p>Return the minimal number of characters that you need to change&nbsp;to divide the string.<\/p>\n\n\n\n<p><strong>A naive interval solution<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">\/\/ O(n^3k)\nalg[i][j][k] = min{ alg[i][l][1] + alg[l + 1][j][k - 1], for l in [i, j - 1]}\n    \nalg[i][j][1] = alg[i + 1][j - 1][1] + s[i] != s[j]<\/code><\/pre>\n\n\n\n<p><strong>A better solution<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">\/\/ O(n^2k)\nalg[i][k] = {alg[j + 1][k - 1] + make_palindrome(s[i:j]), for j in [i, n - 2]}\n\nalg[i][1] = make_palindrome(s[i:n])\n\nmake_palindrome[i][j] = make_palindrome[i + 1][j - 1] + (s[i] != s[j])<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\"><a rel=\"noreferrer noopener\" href=\"https:\/\/leetcode.com\/problems\/palindrome-partitioning-iii\/\" target=\"_blank\"><\/a><a href=\"https:\/\/leetcode.com\/problems\/count-different-palindromic-subsequences\/solution\/\" target=\"_blank\" rel=\"noreferrer noopener\">LC 730.<\/a> Count Different Palindromic Subsequences<\/h4>\n\n\n\n<p>Difficulty: 7 points<\/p>\n\n\n\n<p>Given a string s, find the number of different non-empty palindromic subsequences in S, and&nbsp;return that number modulo&nbsp;<code>10^9 + 7<\/code>. Each character&nbsp;<code>s[i]<\/code>&nbsp;will be in the set&nbsp;<code>{'a', 'b', 'c', 'd'}<\/code>.<\/p>\n\n\n\n<p>The problem is difficult since the subsequences need to be unique. We define <code>alg[i][j][k]<\/code> so that it counts the different palindromic subsequences among <code>s[i,...,j]<\/code> and we expect <code>s[i]<\/code> and <code>s[j]<\/code> to be <code>'a' + c<\/code>.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">alg[i][j][c]\n  1. if s[i] == 'a' + c &amp;&amp; s[j] == 'a' + c: 2 + alg[i + 1][j - 1][0,1,2,3] ('a' + 'aa' + 'a, ... ,a')\n  2. else if s[i] != 'a' + c: alg[i + 1][j][k]\n  3. else if s[j] != 'a' + c: alg[i][j - 1][k]\n  4. else: alg[i + 1][j - 1][k] \n    \n\/\/ alg[i][i][c] = s[i] == 'a' + c\n\/\/ alg[i][i + 1][c] = \n    \/\/  1. if s[i] == 'a' + c &amp;&amp; s[i + 1] == 'a' + c: 2\n    \/\/  2. else if s[i] == 'a' + c: 1\n    \/\/  3. else if s[i + 1] == 'a' + c: 1\n    \/\/  4. else: 0<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\"><a rel=\"noreferrer noopener\" href=\"https:\/\/leetcode.com\/problems\/palindrome-removal\/\" target=\"_blank\">LC 1246.<\/a> Palindrome Removal<\/h4>\n\n\n\n<p>Difficulty: 6-7 points<\/p>\n\n\n\n<p>Given an integer array\u00a0<code>arr<\/code>, in one move you can select a\u00a0palindromic\u00a0subarray\u00a0<code>arr[i], arr[i+1], ..., arr[j]<\/code>\u00a0where\u00a0<code>i &lt;= j<\/code>, and remove that subarray from the given array. Note that after removing a subarray, the elements on the left and on the right of that subarray move to fill the gap left by the removal. Return the minimum number of moves needed\u00a0to remove all numbers from the array.<\/p>\n\n\n\n<p>The first glance might make one feel like it is a dynamic &amp; interval DP problem. However, the thought of dynamic is too complex. Think in this way, if <code>arr[i] == arr[j]<\/code>, we know the problem <code>alg[i][j]<\/code> is the same as <code>alg[i + 1][j - 1]<\/code>, since any subarray in range <code>arr[i+1, j-1]<\/code> could be a new subarray by adding one characters in both sides without any cost. If <code>arr[i]!=arr[j]<\/code>, we could delete a single character, or find a <code>arr[k]<\/code> to make <code>arr[k]==arr[i]<\/code> or <code>arr[k]==arr[j]<\/code>.  These are the two only ways for <code>arr[i]<\/code> or <code>arr[j]<\/code>, since it must be deleted alone or in a subarray. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">alg[i][j] = \n  1. if arr[i] == arr[j]:\n       alg[i + 1][j - 1]\n  2. alg[i][k] + alg[k + 1][j] if arr[i] == arr[k] || arr[k + 1] == arr[j] for k in [i + 1, ... , j - 1]\n  3. 1 + alg[i + 1][j]\n  4. 1 + alg[i][j - 1]\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Summary In this post, I will introduce some problems related to palindrome and dynamic programming. A palindrome has a property that, if we add two equal characters in both side of it, it is still a palindrome. OJ Details LC 1278 Palindrome Partitioning III Difficulty: 6-7 points Given a string&nbsp;s&nbsp;containing lowercase letters and an integer&nbsp;k&#8230;.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,55],"tags":[],"class_list":["post-893","post","type-post","status-publish","format-standard","hentry","category-alg","category-dp-in-linear-structures"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/893","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=893"}],"version-history":[{"count":8,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/893\/revisions"}],"predecessor-version":[{"id":1029,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/893\/revisions\/1029"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=893"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=893"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=893"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}