LeetCode 1340. 跳躍游戲 V（困難）

題目描述

給你一個整數數組?arr?和一個整數?d?。每一步你可以從下標?i?跳到：

i + x?，其中?i + x < arr.length?且?0 < x <= d?。
i - x?，其中?i - x >= 0?且?0 < x <= d?。

除此以外，你從下標?i?跳到下標?j?需要滿足：arr[i] > arr[j]?且?arr[i] > arr[k]?，其中下標?k?是所有?i?到?j?之間的數字（更正式的，min(i, j) < k < max(i, j)）。

你可以選擇數組的任意下標開始跳躍。請你返回你?最多?可以訪問多少個下標。

請注意，任何時刻你都不能跳到數組的外面。

示例 1：

輸入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
輸出：4
解釋：你可以從下標 10 出發，然后如上圖依次經過 10 --> 8 --> 6 --> 7 。
注意，如果你從下標 6 開始，你只能跳到下標 7 處。你不能跳到下標 5 處因為 13 > 9 。你也不能跳到下標 4 處，因為下標 5 在下標 4 和 6 之間且 13 > 9 。
類似的，你不能從下標 3 處跳到下標 2 或者下標 1 處。

示例 2：

輸入：arr = [3,3,3,3,3], d = 3
輸出：1
解釋：你可以從任意下標處開始且你永遠無法跳到任何其他坐標。

示例 3：

輸入：arr = [7,6,5,4,3,2,1], d = 1
輸出：7
解釋：從下標 0 處開始，你可以按照數值從大到小，訪問所有的下標。

示例 4：

輸入：arr = [7,1,7,1,7,1], d = 2
輸出：2

示例 5：

輸入：arr = [66], d = 1
輸出：1

提示：

1 <= arr.length <= 1000
1 <= arr[i] <= 10^5
1 <= d <= arr.length

問題分析

這道題是跳躍游戲系列的第五題，有以下特點：

跳躍規則：
- 可以向左或向右跳躍，跳躍距離范圍是?[1, d]
- 只能從高處往低處跳（arr[i] >?arr[j]）
- 跳躍路徑上的所有點都必須比起點低（arr[i] > arr[k]，對于所有 i 到 j 之間的 k）
目標：找出從任意起點出發，最多可以訪問多少個下標。
關鍵點：
- 可以從任意下標開始
- 需要計算的是最大訪問點數，而不是是否能到達某個特定目標

這個問題適合使用動態規劃來解決，因為跳躍決策具有重疊子問題的性質。同時，由于跳躍的方向性（只能從高處跳到低處），我們可以按高度排序來確定解決問題的順序。

解題思路

動態規劃 + 記憶化搜索

我們可以定義?dp[i]?表示從下標?i?開始跳躍，最多可以訪問的下標數量（包括起點自身）。

遞推關系如下：

對于每個下標?i，我們嘗試向左或向右跳躍距離?x（其中?1 <= x <= d）
如果可以跳到下標?j，那么?dp[i] = max(dp[i],?1 + dp[j])

由于跳躍方向是從高到低，我們需要確保先計算出較低位置的 dp 值，再計算較高位置的 dp?值。一種方法是使用記憶化搜索（也稱為自頂向下的動態規劃）。

算法步驟

創建一個?dp?數組，dp[i]?表示從下標?i?開始最多可以訪問的下標數量
將所有?dp[i]?初始化為 1（至少可以訪問自身）
使用記憶化搜索，對每個下標?i：
- 嘗試向左或向右跳躍距離?x（1 <= x <=?d）
- 檢查跳躍條件：目標位置在數組范圍內，且路徑上所有點都比起點低
- 如果可以跳到下標?j，則?dp[i] = max(dp[i], 1 + dp[j])
返回所有?dp[i]?中的最大值

算法過程

以示例1為例：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2

讓我們跟蹤從下標10開始的DFS過程（這是最優起點）：

初始化：
- dp[10] = 1（至少可以訪問自身）
- 當前下標：10，對應值：12

嘗試向左跳：
- 檢查下標10-1=9：arr[10] > arr[9]?(12 > 6) ?
  - 遞歸計算?dp[9]
  - dp[9] = 1（至少可以訪問自身）
  - 由于沒有可跳的地方，dp[9] =?1
- 檢查下標10-2=8：arr[10] > arr[8]?(12 > 10)??
  - 遞歸計算?dp[8]
  - dp[8] = 1
  - 檢查下標8-1=7：arr[8] > arr[7]?(10 > 7)??
    - 遞歸計算?dp[7]
    - dp[7] = 1
    - 檢查下標7-1=6：arr[7] > arr[6]?(7?< 9) ? 不能跳
    - 檢查下標7-2=5：超出范圍(d=2)
  - 所以?dp[7] = 1
  - 更新?dp[8] = 1?+ dp[7] =?2
  - 檢查下標8-2=6：arr[8] >?arr[6]?(10 > 9)??
    - 已計算?dp[6]?= 1（沒有可跳的地方）
- 更新?dp[8] = max(2, 1+1) = 2
- 更新?dp[10] = max(1, 1+dp[8]) = 1+2 =?3

最終路徑：
- 下標10 -> 下標8 -> 下標7 -> 可能的終點（無法繼續跳躍）
- 或者下標10 -> 下標8 -> 下標6 -> 可能的終點
- 最多訪問4個下標（包括起點10）

事實上，完整的最優路徑是：10 ->?8 -> 6 -> 7，總共訪問4個下標。

詳細代碼實現

Java 實現

class Solution {private int[] dp;private int[] arr;private int d;public int maxJumps(int[] arr, int d) {int n = arr.length;this.arr = arr;this.d = d;this.dp = new int[n];// 初始化dp數組，每個位置至少可以訪問自身Arrays.fill(dp, -1);int maxVisited = 0;for (int i = 0; i < n; i++) {maxVisited = Math.max(maxVisited, dfs(i));}return maxVisited;}private int dfs(int i) {// 如果已經計算過，直接返回if (dp[i] != -1) {return dp[i];}// 至少可以訪問自身dp[i] = 1;// 嘗試向右跳for (int j = i + 1; j <= Math.min(i + d, arr.length - 1); j++) {// 檢查跳躍條件if (arr[i] <= arr[j]) {break;}// 檢查路徑上的所有點boolean canJump = true;for (int k = i + 1; k < j; k++) {if (arr[k] >= arr[i]) {canJump = false;break;}}if (canJump) {dp[i] = Math.max(dp[i], 1 + dfs(j));}}// 嘗試向左跳for (int j = i - 1; j >= Math.max(i - d, 0); j--) {// 檢查跳躍條件if (arr[i] <= arr[j]) {break;}// 檢查路徑上的所有點boolean canJump = true;for (int k = i - 1; k > j; k--) {if (arr[k] >= arr[i]) {canJump = false;break;}}if (canJump) {dp[i] = Math.max(dp[i], 1 + dfs(j));}}return dp[i];}
}

C# 實現

public class Solution {private int[] dp;private int[] arr;private int d;public int MaxJumps(int[] arr, int d) {int n = arr.Length;this.arr = arr;this.d = d;this.dp = new int[n];// 初始化dp數組for (int i = 0; i < n; i++) {dp[i] = -1;}int maxVisited = 0;for (int i = 0; i < n; i++) {maxVisited = Math.Max(maxVisited, Dfs(i));}return maxVisited;}private int Dfs(int i) {// 如果已經計算過，直接返回if (dp[i] != -1) {return dp[i];}// 至少可以訪問自身dp[i] = 1;// 嘗試向右跳for (int j = i + 1; j <= Math.Min(i + d, arr.Length - 1); j++) {// 檢查跳躍條件if (arr[i] <= arr[j]) {break;}// 檢查路徑上的所有點bool canJump = true;for (int k = i + 1; k < j; k++) {if (arr[k] >= arr[i]) {canJump = false;break;}}if (canJump) {dp[i] = Math.Max(dp[i], 1 + Dfs(j));}}// 嘗試向左跳for (int j = i - 1; j >= Math.Max(i - d, 0); j--) {// 檢查跳躍條件if (arr[i] <= arr[j]) {break;}// 檢查路徑上的所有點bool canJump = true;for (int k = i - 1; k > j; k--) {if (arr[k] >= arr[i]) {canJump = false;break;}}if (canJump) {dp[i] = Math.Max(dp[i], 1 + Dfs(j));}}return dp[i];}
}

復雜度分析

時間復雜度：O(n2)，其中n是數組的長度。在最壞情況下，對于每個位置，我們需要檢查最多2d個可能的跳躍目標，總時間復雜度為O(n * d)。由于d最大可達n，所以最壞情況下時間復雜度是O(n2)。

空間復雜度：O(n)，主要用于存儲dp數組和遞歸調用棧。

優化：單調棧方法

上面的實現中，檢查路徑上的所有點是否都比起點低的時間復雜度是?O(d)，我們可以使用單調棧來優化這一過程，降低時間復雜度。

Java 實現

class Solution {public int maxJumps(int[] arr, int d) {int n = arr.length;int[] dp = new int[n];Arrays.fill(dp, -1);// 將下標按照高度排序，從低到高處理Integer[] indices = new Integer[n];for (int i = 0; i < n; i++) {indices[i] = i;}Arrays.sort(indices, (a, b) -> arr[a] - arr[b]);int maxVisited = 0;for (int idx : indices) {maxVisited = Math.max(maxVisited, dfs(arr, d, idx, dp));}return maxVisited;}private int dfs(int[] arr, int d, int i, int[] dp) {if (dp[i] != -1) {return dp[i];}dp[i] = 1; // 至少可以訪問自身// 向右跳for (int j = i + 1; j <= Math.min(i + d, arr.length - 1); j++) {if (arr[i] > arr[j]) {dp[i] = Math.max(dp[i], 1 + dfs(arr, d, j, dp));}// 如果遇到更高或相等的點，則無法繼續向右if (arr[j] >= arr[i]) {break;}}// 向左跳for (int j = i - 1; j >= Math.max(i - d, 0); j--) {if (arr[i] > arr[j]) {dp[i] = Math.max(dp[i], 1 + dfs(arr, d, j, dp));}// 如果遇到更高或相等的點，則無法繼續向左if (arr[j] >= arr[i]) {break;}}return dp[i];}
}

C#實現

public class Solution {public int MaxJumps(int[] arr, int d) {int n = arr.Length;int[] dp = new int[n];// 初始化dp數組，所有值設為-1表示未計算for (int i = 0; i < n; i++) {dp[i] = -1;}// 將下標按照高度排序，從低到高處理int[] indices = new int[n];for (int i = 0; i < n; i++) {indices[i] = i;}Array.Sort(indices, (a, b) => arr[a] - arr[b]);int maxVisited = 0;foreach (int idx in indices) {maxVisited = Math.Max(maxVisited, Dfs(arr, d, idx, dp));}return maxVisited;}private int Dfs(int[] arr, int d, int i, int[] dp) {// 如果已經計算過，直接返回if (dp[i] != -1) {return dp[i];}// 至少可以訪問自身dp[i] = 1;// 向右跳for (int j = i + 1; j <= Math.Min(i + d, arr.Length - 1); j++) {if (arr[i] > arr[j]) {dp[i] = Math.Max(dp[i], 1 + Dfs(arr, d, j, dp));}// 如果遇到更高或相等的點，則無法繼續向右if (arr[j] >= arr[i]) {break;}}// 向左跳for (int j = i - 1; j >= Math.Max(i - d, 0); j--) {if (arr[i] > arr[j]) {dp[i] = Math.Max(dp[i], 1 + Dfs(arr, d, j, dp));}// 如果遇到更高或相等的點，則無法繼續向左if (arr[j] >= arr[i]) {break;}}return dp[i];}
}