{"id":10060,"date":"2023-07-11T18:27:39","date_gmt":"2023-07-12T01:27:39","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10060"},"modified":"2023-07-11T18:30:39","modified_gmt":"2023-07-12T01:30:39","slug":"leetcode-2770-maximum-number-of-jumps-to-reach-the-last-index","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-2770-maximum-number-of-jumps-to-reach-the-last-index\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2770. Maximum Number of Jumps to Reach the Last Index"},"content":{"rendered":"\n<p>You are given a&nbsp;<strong>0-indexed<\/strong>&nbsp;array&nbsp;<code>nums<\/code>&nbsp;of&nbsp;<code>n<\/code>&nbsp;integers and an integer&nbsp;<code>target<\/code>.<\/p>\n\n\n\n<p>You are initially positioned at index&nbsp;<code>0<\/code>. In one step, you can jump from index&nbsp;<code>i<\/code>&nbsp;to any index&nbsp;<code>j<\/code>&nbsp;such that:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>0 &lt;= i &lt; j &lt; n<\/code><\/li><li><code>-target &lt;= nums[j] - nums[i] &lt;= target<\/code><\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>maximum number of jumps<\/strong>&nbsp;you can make to reach index<\/em>&nbsp;<code>n - 1<\/code>.<\/p>\n\n\n\n<p>If there is no way to reach index&nbsp;<code>n - 1<\/code>, return&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,3,6,4,1,2], target = 2\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:\n- Jump from index 0 to index 1. \n- Jump from index 1 to index 3.\n- Jump from index 3 to index 5.\nIt can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3. <\/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> nums = [1,3,6,4,1,2], target = 3\n<strong>Output:<\/strong> 5\n<strong>Explanation:<\/strong> To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:\n- Jump from index 0 to index 1.\n- Jump from index 1 to index 2.\n- Jump from index 2 to index 3.\n- Jump from index 3 to index 4.\n- Jump from index 4 to index 5.\nIt can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5. <\/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> nums = [1,3,6,4,1,2], target = 0\n<strong>Output:<\/strong> -1\n<strong>Explanation:<\/strong> It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1. \n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= nums.length == n &lt;= 1000<\/code><\/li><li><code>-10<sup>9<\/sup>&nbsp;&lt;= nums[i]&nbsp;&lt;= 10<sup>9<\/sup><\/code><\/li><li><code>0 &lt;= target &lt;= 2 * 10<sup>9<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<p>Let dp(i) denotes the maximum jumps from index i to index n-1.<\/p>\n\n\n\n<p>For each index i, try jumping to all possible index j.<\/p>\n\n\n\n<p>dp(i) = max(1 + dp(j)) if j &gt; i and abs(nums[j] &#8211; nums[i) &lt;= target else -1<\/p>\n\n\n\n<p>Time complexity: O(n<sup>2<\/sup>)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def maximumJumps(self, nums: List[int], target: int) -> int:\n    n = len(nums)\n    @cache\n    def dp(i):\n      if i == n - 1: return 0\n      ans = -1\n      for j in range(i + 1, n):\n        if abs(nums[j] - nums[i]) <= target and dp(j) != -1:\n          ans = max(ans, 1 + dp(j))\n      return ans\n    \n    return dp(0)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a&nbsp;0-indexed&nbsp;array&nbsp;nums&nbsp;of&nbsp;n&nbsp;integers and an integer&nbsp;target. You are initially positioned at index&nbsp;0. In one step, you can jump from index&nbsp;i&nbsp;to any index&nbsp;j&nbsp;such that: 0&#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,432,177],"class_list":["post-10060","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-jump","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10060","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=10060"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10060\/revisions"}],"predecessor-version":[{"id":10062,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10060\/revisions\/10062"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10060"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10060"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10060"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}