{"id":6237,"date":"2020-02-01T23:15:58","date_gmt":"2020-02-02T07:15:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6237"},"modified":"2020-02-02T00:34:55","modified_gmt":"2020-02-02T08:34:55","slug":"leetcode-1344-jump-game-v","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1344-jump-game-v\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1344. Jump Game V"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1344. Jump Game V - \u5237\u9898\u627e\u5de5\u4f5c EP305\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/y5hRO6NvOHg?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given an array of&nbsp;integers&nbsp;<code>arr<\/code>&nbsp;and an integer&nbsp;<code>d<\/code>. In one step you can jump from index&nbsp;<code>i<\/code>&nbsp;to index:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>i + x<\/code>&nbsp;where:&nbsp;<code>i + x &lt; arr.length<\/code>&nbsp;and&nbsp;<code>0 &lt;&nbsp;x &lt;= d<\/code>.<\/li><li><code>i - x<\/code>&nbsp;where:&nbsp;<code>i - x &gt;= 0<\/code>&nbsp;and&nbsp;<code>0 &lt;&nbsp;x &lt;= d<\/code>.<\/li><\/ul>\n\n\n\n<p>In addition, you can only jump from index&nbsp;<code>i<\/code>&nbsp;to index&nbsp;<code>j<\/code>&nbsp;if&nbsp;<code>arr[i] &gt; arr[j]<\/code>&nbsp;and&nbsp;<code>arr[i] &gt; arr[k]<\/code>&nbsp;for all indices&nbsp;<code>k<\/code>&nbsp;between&nbsp;<code>i<\/code>&nbsp;and&nbsp;<code>j<\/code>&nbsp;(More formally&nbsp;<code>min(i,&nbsp;j) &lt; k &lt; max(i, j)<\/code>).<\/p>\n\n\n\n<p>You can choose any index of the array and start jumping. Return&nbsp;<em>the maximum number of indices<\/em>&nbsp;you can visit.<\/p>\n\n\n\n<p>Notice that you can not jump outside of the array at any time.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/01\/23\/meta-chart.jpeg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> You can start at index 10. You can jump 10 --&gt; 8 --&gt; 6 --&gt; 7 as shown.\nNote that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 &gt; 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 &gt; 9.\nSimilarly You cannot jump from index 3 to index 2 or index 1.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [3,3,3,3,3], d = 3\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> You can start at any index. You always cannot jump to any index.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [7,6,5,4,3,2,1], d = 1\n<strong>Output:<\/strong> 7\n<strong>Explanation:<\/strong> Start at index 0. You can visit all the indicies. \n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [7,1,7,1,7,1], d = 2\n<strong>Output:<\/strong> 2\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [66], d = 1\n<strong>Output:<\/strong> 1\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= arr.length &lt;= 1000<\/code><\/li><li><code>1 &lt;= arr[i] &lt;= 10^5<\/code><\/li><li><code>1 &lt;= d &lt;= arr.length<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Recursion w\/ Memoization<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/02\/1344-ep305-1.png\" alt=\"\" class=\"wp-image-6241\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/02\/1344-ep305-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/02\/1344-ep305-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/02\/1344-ep305-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp(i) = max{1, max{dp(j) + 1}}, if i can jump to j.<br>ans = max(dp(i))<\/p>\n\n\n\n<p>Time complexity: O(n*d)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxJumps(vector<int>& a, int d) {\n    int n = a.size();    \n    vector<int> m(n);\n    function<int(int)> dp = [&](int i) {\n      if (m[i]) return m[i];\n      int ans = 1;\n      for (int j = i + 1; j <= min(n - 1, i + d) &#038;&#038; a[i] > a[j]; ++j) \n        ans = max(ans, dp(j) + 1);\n      for (int j = i - 1; j >= max(0, i - d) && a[i] > a[j]; --j)\n        ans = max(ans, dp(j) + 1);        \n      return m[i] = ans;\n    };\n    \n    int ans = 0;\n    for (int i = 0; i < n; ++i)  \n      ans = max(ans, dp(i));    \n    return ans;\n  }\n};\n\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: DP<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/02\/1344-ep305-2.png\" alt=\"\" class=\"wp-image-6242\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/02\/1344-ep305-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/02\/1344-ep305-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/02\/1344-ep305-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Time complexity: O(nlogn + n*d)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxJumps(vector<int>& a, int d) {\n    const int n = a.size();\n    vector<pair<int, int>> m(n); \/\/ <height, index>\n    for (int i = 0; i < n; ++i)\n      m[i] = {a[i], i};    \n    \/\/ Solve from the lowest bar.\n    sort(begin(m), end(m));    \n\n    vector<int> dp(n, 1);\n    for (auto [v, i] : m) {      \n      for (int j = i + 1; j <= min(n - 1, i + d) &#038;&#038; a[i] > a[j]; ++j) \n        dp[i] = max(dp[i], dp[j] + 1);\n      for (int j = i - 1; j >= max(0, i - d) && a[i] > a[j]; --j)\n        dp[i] = max(dp[i], dp[j] + 1);\n    }\n    \n    return *max_element(begin(dp), end(dp));\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an array of&nbsp;integers&nbsp;arr&nbsp;and an integer&nbsp;d. In one step you can jump from index&nbsp;i&nbsp;to index: i + x&nbsp;where:&nbsp;i + x &lt; arr.length&nbsp;and&nbsp;0 &lt;&nbsp;x &lt;= d.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,217,546],"class_list":["post-6237","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-onk","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6237","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6237"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6237\/revisions"}],"predecessor-version":[{"id":6243,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6237\/revisions\/6243"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6237"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6237"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6237"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}