1340. Jump Game V

題目 / Problem

給定一個整數陣列 arr 和一個整數 d。從索引 i 出發，一步可以跳到： - i + x，條件是 i + x < arr.length 且 0 < x <= d（往右跳）。 - i - x，條件是 i - x >= 0 且 0 < x <= d（往左跳）。

此外，只有當 arr[i] > arr[j]，而且對於 i 和 j 之間的所有索引 k（即 min(i,j) < k < max(i,j)）都有 arr[i] > arr[k] 時，才能從 i 跳到 j。你可以選任意索引作為起點，回傳最多能造訪的索引數目。注意你永遠不能跳出陣列。

You are given an integer array arr and an integer d. From index i you may jump to: - i + x where i + x < arr.length and 0 < x <= d (jump right). - i - x where i - x >= 0 and 0 < x <= d (jump left).

You may only jump from i to j if arr[i] > arr[j] and arr[i] > arr[k] for every index k strictly between i and j. You may start at any index. Return the maximum number of indices you can visit. You can never jump outside the array.

Constraints / 限制 - 1 <= arr.length <= 1000 - 1 <= arr[i] <= 10^5 - 1 <= d <= arr.length

Worked example / 範例

arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2  ->  4

從索引 10 出發：10 → 8 → 6 → 7，共造訪 4 個索引。 Starting at index 10: 10 → 8 → 6 → 7, visiting 4 indices.

名詞解釋 / Glossary

• 動態規劃 / Dynamic Programming (DP): 把大問題拆成可重複利用的小問題，並把每個小問題的答案存起來避免重算。An approach that breaks a big problem into smaller overlapping sub-problems and stores each sub-answer so it is computed only once.
• 記憶化搜尋 / Memoized recursion: 一種 DP 實作方式：用遞迴函式計算答案，第一次算出後存進陣列；之後再被問到同一個索引就直接回傳。A way to implement DP: a recursive function computes an answer, caches it in an array, and returns the cached value on later calls for the same input.
• 遞迴 / Recursion: 函式呼叫自己來解決更小的子問題，直到遇到不需再呼叫的「基底情況」。A function that calls itself on smaller sub-problems until it reaches a base case that needs no further calls.
• 基底情況 / Base case: 遞迴中可以直接得到答案、不再往下呼叫的情形。這裡是「某索引哪裡都跳不了」，答案為 1。The case where recursion stops because the answer is immediate — here, an index from which no jump is possible, giving 1.
• dp[i]: 定義為「從索引 i 出發（含 i 本身）最多能造訪幾個索引」。Defined as the maximum number of indices you can visit when starting at index i (counting i itself).
• 指標 / Pointer (C): 一個存放記憶體位址的變數；int* arr 表示 arr 指向一段整數。arr[i] 等同於讀取該段中第 i 個整數。A variable holding a memory address; int* arr points at a block of ints, and arr[i] reads the i-th int in that block.
• calloc / free: calloc(n, size) 配置一塊記憶體並把每個位元組設成 0；用完要用 free 歸還，否則記憶體外洩。calloc allocates memory pre-filled with zeros; free releases it to avoid memory leaks.

思路

最直覺的想法是「窮舉所有路徑」：從每個索引出發，嘗試每一種可能的跳法，記錄能走多遠。但跳躍路徑會分岔又分岔，重複造訪同一個索引很多次，時間會爆炸。關鍵觀察是：從某個索引 i 出發能走多遠，只跟 i 本身有關，跟你是怎麼走到 i 的無關。所以我們定義 dp[i] = 從 i 出發（含自己）最多能造訪的索引數，這個值算一次就能反覆使用。轉移式是 dp[i] = 1 + max(dp[j])，其中 j 是所有能從 i 合法跳到的索引；如果 i 哪裡都跳不了，dp[i] = 1。怎麼找合法的 j？往右掃 x = 1..d，一旦遇到某個高度 >= arr[i] 的索引就立刻停止——因為那個索引要嘛本身不滿足 arr[i] > arr[j]，要嘛它擋住了後面所有更遠的跳躍（它成了中間更高的 k）。往左同理。我們用記憶化遞迴：第一次算 dp[i] 時把結果存進 memo[i]，之後直接取用，保證每個索引只算一次。最後答案是所有 dp[i] 的最大值。

The naive idea is to enumerate every path: start from each index and try all jump sequences. But paths branch repeatedly and revisit indices, so the work explodes. The key insight is that how far you can travel starting from index i depends only on i, not on how you arrived there. So define dp[i] = the maximum number of indices reachable starting at i (including i itself); once computed, it can be reused. The transition is dp[i] = 1 + max(dp[j]) over every index j you can legally reach from i, and dp[i] = 1 when no jump is possible. To find the legal js, scan rightward x = 1..d and stop the moment you hit a height >= arr[i]: that index either fails the arr[i] > arr[j] rule itself, or it is a taller blocker k that prevents any farther jump in that direction. Scan leftward the same way. We use memoized recursion: the first time we compute dp[i] we store it in memo[i] and reuse it afterward, so each index is solved exactly once. The answer is the maximum dp[i] over all i.

逐步走查 / Walkthrough

以範例 arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2 為例。索引與值：

我們逐步計算需要的 dp 值（按遞迴展開順序）/ computing the dp values needed, in recursion order:

從索引 10 出發得到 dp[10] = 4，正好對應路徑 10 → 8 → 6 → 7。對其餘起點同樣計算後，所有 dp[i] 的最大值就是 4。

Starting at index 10 gives dp[10] = 4, matching the path 10 → 8 → 6 → 7. After computing dp for the remaining starts, the maximum over all dp[i] is 4.

Solution — C

// 演算法：記憶化 DP。dp[i] = 從 i 出發最多造訪的索引數。
// Algorithm: memoized DP. dp[i] = max indices visited starting at i.
// 往兩側各掃最多 d 步，碰到 >= arr[i] 的高度就停（被擋住）。答案 = max(dp[i])。
// Scan up to d steps each side, stopping at any height >= arr[i] (blocked). Answer = max(dp[i]).

#include <stdlib.h>   // 提供 calloc / free / NULL / Provides calloc / free / NULL

// 遞迴計算 dp[i]，結果存進 memo / Recursively compute dp[i], caching in memo
int dfs(int i, int* arr, int n, int d, int* memo) {
    if (memo[i] != 0) return memo[i];   // 已算過就直接回傳（dp 永遠 >=1，0 代表未算）/ cached? return it (dp is always >=1, so 0 means "not computed")

    int best = 1;                       // 至少能造訪自己這個索引 / at minimum we visit index i itself

    // 往右掃：x 從 1 到 d，且不超出邊界 / scan right: x = 1..d, staying in bounds
    for (int x = 1; x <= d && i + x < n; x++) {
        int j = i + x;                  // 候選目標索引 / candidate target index
        if (arr[j] >= arr[i]) break;    // 遇到不矮於 arr[i] 的高度就停：要嘛跳不過去，要嘛它擋住後面 / hit a height >= arr[i]: either illegal target or a blocker — stop
        int sub = 1 + dfs(j, arr, n, d, memo); // 從 j 繼續，再加上 i 這一步 / continue from j, plus the step into i
        if (sub > best) best = sub;     // 取較大的路徑長度 / keep the longer reach
    }

    // 往左掃：對稱地處理 / scan left: symmetric handling
    for (int x = 1; x <= d && i - x >= 0; x++) {
        int j = i - x;                  // 候選目標索引（左側）/ candidate target on the left
        if (arr[j] >= arr[i]) break;    // 同樣遇到障礙就停 / stop at the first blocker
        int sub = 1 + dfs(j, arr, n, d, memo);
        if (sub > best) best = sub;
    }

    memo[i] = best;                     // 存起來，下次直接用 / cache so we never recompute
    return best;
}

int maxJumps(int* arr, int arrSize, int d) {
    // calloc 配置 arrSize 個 int 並全部設為 0（代表「尚未計算」）/ allocate arrSize ints, all zeroed (meaning "not yet computed")
    int* memo = (int*)calloc(arrSize, sizeof(int));

    int ans = 0;                        // 目前找到的最大造訪數 / best answer so far
    for (int i = 0; i < arrSize; i++) { // 嘗試以每個索引為起點 / try every index as a starting point
        int r = dfs(i, arr, arrSize, d, memo);
        if (r > ans) ans = r;           // 更新全域最大值 / update the global maximum
    }

    free(memo);                         // 歸還記憶體，避免外洩 / release memory to avoid a leak
    return ans;
}

Solution — C++

// 演算法同 C 版：記憶化 DP，dp[i] = 從 i 出發最多造訪的索引數。
// Same algorithm as the C version: memoized DP, dp[i] = max indices visited from i.
// 兩側各掃 d 步，遇到 >= arr[i] 即停；答案是所有 dp[i] 的最大值。
// Scan d steps each side, stop at any height >= arr[i]; answer is max over all dp[i].

#include <vector>      // std::vector：可自動管理大小的動態陣列 / dynamic array that manages its own memory
#include <algorithm>   // std::max：回傳兩數中的較大者 / returns the larger of two values

class Solution {
public:
    int maxJumps(std::vector<int>& arr, int d) {
        int n = arr.size();                 // 陣列長度 / length of the array
        std::vector<int> memo(n, 0);        // 全部初始化為 0，代表「未計算」/ all zeros, meaning "not computed"

        int ans = 0;                        // 全域最大造訪數 / global best
        for (int i = 0; i < n; ++i)         // 以每個索引為起點 / try each index as a start
            ans = std::max(ans, dfs(i, arr, d, memo)); // 取較大者更新答案 / keep the larger
        return ans;
    }

private:
    // dfs 計算並快取 dp[i] / dfs computes and caches dp[i]
    int dfs(int i, std::vector<int>& arr, int d, std::vector<int>& memo) {
        if (memo[i] != 0) return memo[i];   // 已算過直接回傳（dp >=1，所以 0=未算）/ return cache (dp >=1, so 0 means unset)

        int n = arr.size();
        int best = 1;                       // 至少造訪自己 / at least visit i itself

        // 往右最多 d 步 / up to d steps to the right
        for (int x = 1; x <= d && i + x < n; ++x) {
            int j = i + x;
            if (arr[j] >= arr[i]) break;    // 障礙：跳不過或被擋 → 停止 / blocker: illegal or blocking → stop
            best = std::max(best, 1 + dfs(j, arr, d, memo)); // 取最長延伸 / take the longest extension
        }

        // 往左最多 d 步 / up to d steps to the left
        for (int x = 1; x <= d && i - x >= 0; ++x) {
            int j = i - x;
            if (arr[j] >= arr[i]) break;
            best = std::max(best, 1 + dfs(j, arr, d, memo));
        }

        return memo[i] = best;              // 一行內存入快取並回傳 / cache and return in one line
    }
};

複雜度 / Complexity

• Time: O(n · d) — 共有 n 個索引，每個 dp[i] 只算一次（記憶化保證）。計算單一 dp[i] 時，往左往右各最多掃 d 步，所以單次是 O(d)，總共 O(n·d)。There are n indices and each dp[i] is computed once (thanks to memoization); each computation scans at most d steps on each side, so O(d) per index and O(n·d) overall.
• Space: O(n) — memo 陣列佔 O(n)；遞迴呼叫堆疊深度最壞也是 O(n)（一條遞減的鏈）。The memo array uses O(n), and the recursion call stack can be O(n) deep in the worst case (a strictly descending chain).

Pitfalls & Edge Cases

• 掃描時的「停止 vs 跳過」/ Break, don't continue: 遇到 arr[j] >= arr[i] 必須 break（停止整個方向），不能 continue。因為那個較高的索引是中間的障礙 k，會擋住它後面所有更遠的目標。用 continue 會錯誤地允許跨越障礙。Hitting arr[j] >= arr[i] must break the whole direction, not continue; that taller index is a blocking k for everything beyond it, and continue would illegally jump over it.
• 「未計算」標記的選擇 / Choosing the "uncomputed" sentinel: 因為任何 dp[i] 至少是 1（造訪自己），用 0 當作「尚未計算」是安全的，不會和真實答案混淆。Since every dp[i] is at least 1 (you always visit the start), using 0 as the "not computed" marker never collides with a real value.
• 邊界條件寫進迴圈 / Bounds inside the loop guard: 迴圈條件 i + x < n 與 i - x >= 0 直接擋住越界存取；少了它會讀到陣列外的記憶體（C 是未定義行為）。The loop guards i + x < n and i - x >= 0 prevent out-of-bounds access; omitting them reads past the array (undefined behavior in C).
• 必須嘗試每個起點 / Try all starting indices: 最佳起點不一定是最高或最低的元素（見範例最佳起點是索引 10 而非最大值 14 所在的索引 2），所以要對所有 i 取 dp[i] 的最大值。The best start is not necessarily the tallest or shortest element (in the example it is index 10, not index 2 which holds the max 14), so you must maximize dp[i] over all i.
• 不會有環 / No cycles: 每次跳躍都要求 arr[i] > arr[j]，高度嚴格遞減，因此不可能跳回已造訪的索引，遞迴一定會終止——不需要額外的 visited 標記。Every jump requires arr[i] > arr[j], so heights strictly decrease and you can never return to a visited index; recursion always terminates with no extra visited set.