2770. Maximum Number of Jumps to Reach the Last Index

題目 / Problem

中文： 給定一個 0-indexed 的整數陣列 nums（長度為 n）和一個整數 target。一開始你站在索引 0。每一步你可以從索引 i 跳到索引 j，條件是： - 0 <= i < j < n - -target <= nums[j] - nums[i] <= target

請回傳你能跳到索引 n - 1 的最大跳躍次數。如果無法到達最後一個位置，回傳 -1。

English: Given a 0-indexed integer array nums of length n and an integer target. You start at index 0. In one step you can jump from i to j if: - 0 <= i < j < n - -target <= nums[j] - nums[i] <= target

Return the maximum number of jumps to reach index n - 1, or -1 if it is impossible.

Constraints: - 2 <= n <= 1000 - -10^9 <= nums[i] <= 10^9 - 0 <= target <= 2 * 10^9

Worked example: nums = [1,3,6,4,1,2], target = 2 → 3. One optimal path: 0 → 1 → 3 → 5.

名詞解釋 / Glossary

• 動態規劃 / Dynamic Programming (DP) — 把大問題拆成重疊的小子問題並把答案存起來，避免重複計算。Solving a problem by breaking it into overlapping subproblems and reusing each subproblem's answer.
• 狀態 / State — DP 中代表「子問題」的變數組合；本題的狀態是「目前停在哪個索引」。The variables describing one subproblem; here it's "which index am I currently standing on".
• 狀態轉移 / Transition — 從一個狀態推到下一個狀態的規則；這裡是 dp[j] = max(dp[j], dp[i] + 1)。The rule that derives one state from a previous one.
• 不可達哨兵值 / Unreachable Sentinel — 用一個特殊值（例如 -1）表示「這個位置從 0 跳不到」。A special value (e.g. -1) marking a state that can never be entered.
• malloc / free（C） — malloc(n * sizeof(T)) 在堆積 (heap) 上配置一塊記憶體並回傳指標；用完要 free 釋放。Allocates and releases heap memory in C.
• std::vector（C++） — 自動管理長度與記憶體的動態陣列，相當於 C 的「malloc + free」打包好。A self-managing dynamic array; no manual free needed.
• std::max — 回傳兩個值中較大的那個。Returns the larger of two values.

思路

最直覺的暴力做法是嘗試所有跳躍順序：從 0 出發遞迴地往後跳，每跳一次就 +1，最後取最大值。但每個位置都可能跳到後面任何一個位置，狀態空間呈指數爆炸，n = 1000 必定逾時。觀察發現「從 0 走到索引 j 的最大跳躍次數」只跟「我在哪一格」有關，跟「我用什麼路線走過來」無關 — 這正是動態規劃的訊號。我們定義 dp[j] = 從索引 0 到 j 的最大跳躍次數，初始化 dp[0] = 0，其他位置設成 -1 代表不可達。對每個 j 從 1 掃到 n-1，再對每個 i < j 檢查 (a) dp[i] 是否可達；(b) |nums[j] - nums[i]| <= target 是否成立。若兩條件都成立，就用 dp[i] + 1 去更新 dp[j]。為什麼可以這樣安全地由小推大？因為 j 只會從 i < j 的位置轉移過來，外層按 j 遞增順序計算時，所有需要的 dp[i] 都已經確定了。最後 dp[n-1] 就是答案；若仍是 -1 表示不可達。

The brute-force idea is to try every jumping sequence recursively from index 0, but the number of paths is exponential and 1000 elements would never finish in time. The key observation is that "the maximum number of jumps to reach index j" depends only on which index we're on — not on the path we took to get there — which is exactly when DP applies. Define dp[j] as the maximum number of jumps from 0 to j, with dp[0] = 0 and all others initialized to -1 (the "unreachable" sentinel). Iterate j from 1 to n-1 and, for each j, scan every earlier i < j: if dp[i] is reachable and |nums[j] - nums[i]| <= target, relax dp[j] = max(dp[j], dp[i] + 1). The order is safe because dp[j] only ever reads from strictly smaller indices, all of which were finalized in previous outer iterations. The answer is dp[n-1] (or -1 if it stayed unreachable). With n <= 1000, the O(n^2) work is comfortably fast.

逐步走查 / Walkthrough

Input: nums = [1, 3, 6, 4, 1, 2], target = 2. Initialize dp = [0, -1, -1, -1, -1, -1].

Final answer = dp[5] = 3. ✅

Solution — C

// 演算法：DP，dp[j] = 從索引 0 跳到 j 的最大次數，-1 表不可達
// Algorithm: DP where dp[j] = max jumps from 0 to j, -1 means unreachable.
// 對每個 j，掃所有 i<j，若 |nums[j]-nums[i]|<=target 則用 dp[i]+1 鬆弛 dp[j]
// For each j, scan every i<j and relax dp[j] = max(dp[j], dp[i]+1) when in range.
// 時間 O(n^2)，空間 O(n)。Time O(n^2), space O(n).

#include <stdlib.h>   // malloc / free 的標頭 / header for malloc and free

int maximumJumps(int* nums, int numsSize, int target) {
    // 在堆積上配置長度為 n 的 int 陣列 / allocate an int array of length n on the heap
    int* dp = (int*)malloc(sizeof(int) * numsSize);

    // 把全部位置先設為 -1，代表「目前還無法從 0 跳到這裡」
    // Initialize every entry to -1, meaning "not yet known to be reachable from 0".
    for (int i = 0; i < numsSize; i++) {
        dp[i] = -1;
    }
    dp[0] = 0;  // 起點本身不需要跳，所以是 0 / starting point needs zero jumps

    // 外層 j：依序計算每個目標索引；因為只往回看 i<j，順序保證子問題已算好
    // Outer loop j: compute each target index in order; since we only look back at i<j,
    // every dp[i] we read has already been finalized.
    for (int j = 1; j < numsSize; j++) {
        // 內層 i：列舉所有可能跳到 j 的前一格 / inner loop: every candidate previous index
        for (int i = 0; i < j; i++) {
            // 若 i 本身就跳不到，當然不能從 i 再跳到 j / skip unreachable predecessors
            if (dp[i] == -1) continue;

            // 用 long 避免兩個 ±1e9 相減在 int 邊界附近的疑慮 (純為教學保險)
            // Use long to dodge any int-edge worries when subtracting two ±1e9 values.
            long diff = (long)nums[j] - (long)nums[i];

            // 條件：差值落在 [-target, target] 區間 / jump is legal iff diff is in range
            if (diff >= -(long)target && diff <= (long)target) {
                // 鬆弛：dp[j] 取「自己」與「從 i 過來再 +1」中較大者
                // Relax: keep the larger of the current dp[j] and dp[i]+1.
                if (dp[i] + 1 > dp[j]) {
                    dp[j] = dp[i] + 1;
                }
            }
        }
    }

    int ans = dp[numsSize - 1];  // 終點的答案（可能仍是 -1）/ answer at the last index
    free(dp);                    // 釋放剛剛 malloc 的記憶體 / release heap memory
    return ans;
}

Solution — C++

// 演算法與 C 版相同：dp[j] 為從 0 到 j 的最大跳躍次數，-1 表不可達
// Same algorithm as the C version: dp[j] = max jumps from 0 to j, -1 = unreachable.
// 用 std::vector 與 std::max 寫得更簡潔 / written with std::vector and std::max for clarity.
// 時間 O(n^2)，空間 O(n)。Time O(n^2), space O(n).

#include <vector>     // std::vector 動態陣列 / dynamic array container
#include <algorithm>  // std::max
using namespace std;

class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();  // n 是陣列長度，型別 int 已足夠 / array length, int suffices

        // vector<int> dp(n, -1)：建立長度 n 的向量，每格初始化為 -1（不可達哨兵）
        // vector<int> dp(n, -1) creates a length-n vector, every slot set to -1 (sentinel).
        vector<int> dp(n, -1);
        dp[0] = 0;  // 起點不用跳 / starting index needs no jumps

        // 由小到大計算每個目標索引 j / fill dp[j] in increasing order of j
        for (int j = 1; j < n; ++j) {
            for (int i = 0; i < j; ++i) {
                if (dp[i] == -1) continue;  // i 不可達就跳過 / skip unreachable i

                // 轉成 long long，徹底避免兩個 1e9 量級整數相減/比較的溢位疑慮
                // Cast to long long to be completely safe against int overflow concerns.
                long long diff = (long long)nums[j] - (long long)nums[i];

                if (diff >= -(long long)target && diff <= (long long)target) {
                    // std::max 回傳兩者較大值，等同於手寫的 if 判斷
                    // std::max returns the larger of the two arguments.
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
        }

        return dp[n - 1];  // 若仍為 -1 表示無法到達 / -1 means terminal index unreachable
    }
};

複雜度 / Complexity

• Time: O(n^2) — 外層 j 走 n 次、內層 i 最多走 j 次，總共約 n*(n-1)/2 次比較。n 是 nums 的長度。The outer loop runs n times and the inner loop up to j times, giving roughly n^2 / 2 constant-work checks. Here n = nums.length.
• Space: O(n) — 只有一個長度為 n 的 dp 陣列；其他都是常數變數。Only the dp array of length n; everything else is a handful of scalar variables.

Pitfalls & Edge Cases

• 回傳 -1，而不是 0 — 不可到達的終點要回 -1，但起點本身需要 0 步，兩者都用 dp 但意義不同。Don't confuse "unreachable" (-1) with "starting point" (0); both live in dp, but mean different things.
• 不可達不能拿來轉移 / Don't relax from unreachable predecessors — 如果忘記 if (dp[i] == -1) continue;，會把 -1 + 1 = 0 誤當成「跳一次就到」，答案會錯。Without the skip, -1 + 1 = 0 looks like a valid one-jump path and corrupts later states.
• 絕對值寫法 / Range check — 條件是 -target <= diff <= target，請勿誤寫成 abs(diff) <= target 後又忘了 target 可能很大 — 雖然數學等價，但拆成兩個比較對初學者更清楚。Mathematically equivalent to abs(diff) <= target, but writing the two comparisons makes the intent clearer.
• 整數溢位 / Integer overflow — nums[i] 可達 ±10^9，差值可到 2 * 10^9；target 上限也是 2 * 10^9。雖然剛好塞得進 32-bit int，但寫成 long/long long 比較最保險，也方便讀者理解我們在意這件事。Edge of the int32 range — using long/long long for the diff avoids subtle bugs and signals the concern.
• target == 0 — 只有「值完全相等」的兩格才能互跳；常常導致無法到達，要正確回傳 -1（見 Example 3）。Only equal-valued indices can jump to each other; often produces the -1 case.
• 記得 free / Memory leak in C — C 版用 malloc 後要 free，否則 LeetCode 雖不會判錯，但是好習慣。Always free what you malloc — leaks won't fail LeetCode but are bad practice.