{"id":898,"date":"2020-04-02T21:13:04","date_gmt":"2020-04-03T04:13:04","guid":{"rendered":"http:\/\/209.126.2.187\/?p=898"},"modified":"2020-04-02T21:15:58","modified_gmt":"2020-04-03T04:15:58","slug":"subarray-dp","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/04\/02\/subarray-dp\/","title":{"rendered":"Subarray & DP"},"content":{"rendered":"\n

Summary <\/h2>\n\n\n\n

In this post, I will introduce some problems related to subarray and dynamic programming. <\/p>\n\n\n\n

The most important thing in subarray is that it is continuous. So usually one dimension of the DP will be chosen as “a subarray starting at index i”. Then we need a separate loop for it to choose the best starting point. <\/p>\n\n\n\n

OJ<\/h2>\n\n\n\n\n\n\n\n\t\n\n\t\n\t\n\t
<\/td>Trick<\/th>Difficulty<\/th>\n<\/tr>\n<\/thead>\n
LC 53 <\/a><\/td>Maximum Subarray Sum<\/td>3 points<\/td>\n<\/tr>\n
LC 644<\/a><\/td>Binary Search Result + Greedy + Maximum Subarray Sum<\/td>6 points<\/td>\n<\/tr>\n
LC 727 <\/a><\/td>DP+Subarray+Subsequence<\/td>6 points<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n

Details<\/h2>\n\n\n\n

Minimum Window Subsequence<\/h4>\n\n\n\n

Given strings\u00a0S<\/code>\u00a0and\u00a0T<\/code>, find the minimum (contiguous)\u00a0substring<\/strong>\u00a0W<\/code>\u00a0of\u00a0S<\/code>, so that\u00a0T<\/code>\u00a0is a\u00a0subsequence<\/strong>\u00a0of\u00a0W<\/code>.<\/p>\n\n\n\n

\/\/ alg[i][j], the shortest subarray starting at i in S contains T[j:] as a subsequence.\n\/\/ alg[i][n] = 0\nalg[i][j] = min{\n  1. 1 + alg[i + 1][j + 1] if S[i] == T[j],\n  2. 1 + alg[i + 1][j],\n}<\/code><\/pre>\n\n\n\n
Since dimension i<\/code> is defined as subarray, we should add 1 even if we don’t want to use the character at i<\/code>. It is wrong if we go with,<\/p>\n\n\n\n
alg[i][j] = min{\n  1. 1 + alg[i + 1][j + 1] if S[i] == T[j],\n  2. alg[i + 1][j],\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
Summary In this post, I will introduce some problems related to subarray and dynamic programming. The most important thing in subarray is that it is continuous. So usually one dimension of the DP will be chosen as “a subarray starting at index i”. Then we need a separate loop for it to choose the best…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-898","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/898","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=898"}],"version-history":[{"count":6,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/898\/revisions"}],"predecessor-version":[{"id":912,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/898\/revisions\/912"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=898"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=898"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=898"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}