{"id":1064,"date":"2020-04-26T10:53:14","date_gmt":"2020-04-26T17:53:14","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1064"},"modified":"2020-05-06T22:03:15","modified_gmt":"2020-05-07T05:03:15","slug":"monotonic-queue-in-dp","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/04\/26\/monotonic-queue-in-dp\/","title":{"rendered":"Monotonic Queue in DP"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Summary<\/h2>\n\n\n\n<p>In this post, I will introduce some DP problems involving the Monotonic Queue.<\/p>\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\/constrained-subset-sum\/\" target=\"_blank\">LC 1425. Constrained Subset Sum<\/a><\/h4>\n\n\n\n<p>It is not difficult to get the following <code>O(n^2)<\/code> solution. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">alg[i] = nums[i] + max {alg[i+j] for j=[1, k]}<\/code><\/pre>\n\n\n\n<p>However, the complexity is not good. What we need for <code>{alg[i+j] for j=[1, k]}<\/code> is only the maximum. So we need to keep tracking the sliding window maximum. An <code>O(nlogn)<\/code> solution is intuitive. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">alg[i] = nums[i] + pq.max\n\/\/ note that we need to invalidate pq when the index_of_max > i + k<\/code><\/pre>\n\n\n\n<p>It is still not enough. Monotonic Queue works perfect for Sliding Window Maximum. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"\" class=\"\">alg[i] = nums[i] + max(0, alg[mq.sliding_window_max()])<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\"><a rel=\"noreferrer noopener\" href=\"https:\/\/leetcode.com\/problems\/jump-game-v\/\" target=\"_blank\">LC 1340. Jump Game V<\/a><\/h4>\n\n\n\n<p>It is not difficult to get the following <code>O(n^2)<\/code> solution.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">alg[i] = max {\n  1 + alg[k] for k in [i - d, i + d]\n}<\/code><\/pre>\n\n\n\n<p>However, the time complexity could be reduced to <code>O(n)<\/code>. We think backwards. For each index <code>i<\/code>, it could be reached by indexes that values are larger. We greedily choose the nearest higher since it leaves more indexes for the rest jumps. Monotonic Queues work perfectly for Sliding Window Nearest Higher Number. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">alg[i] = 1 + max{\n   alg[left_nearest_higher[i]],\n   alg[right_nearest_higher[i]]\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Summary In this post, I will introduce some DP problems involving the Monotonic Queue. Details LC 1425. Constrained Subset Sum It is not difficult to get the following O(n^2) solution. However, the complexity is not good. What we need for {alg[i+j] for j=[1, k]} is only the maximum. So we need to keep tracking the&#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,52],"tags":[],"class_list":["post-1064","post","type-post","status-publish","format-standard","hentry","category-alg","category-dp-in-linear-structures","category-monotonic-queue"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1064","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=1064"}],"version-history":[{"count":5,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1064\/revisions"}],"predecessor-version":[{"id":1260,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1064\/revisions\/1260"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1064"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1064"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1064"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}