# 到達終點的最小跳數 > 原文： [https://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/](https://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/) 給定一個整數數組，其中每個元素代表可以從該元素進行的最大步數。 編寫一個函數以返回到達數組末尾（從第一個元素開始）的最小跳轉數。 如果一個元素為 0，則不能在該元素中移動。 **示例**： ``` Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} Output: 3 (1-> 3 -> 8 -> 9) Explanation: Jump from 1st element to 2nd element as there is only 1 step, now there are three options 5, 8 or 9\. If 8 or 9 is chosen then the end node 9 can be reached. So 3 jumps are made. Input: arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} Output: 10 Explanation: In every step a jump is needed so the count of jumps is 10. ``` 第一個元素是 1，因此只能轉到 3。第二個元素是 3，因此最多可以執行 3 個步驟，例如到 5 或 8 或 9。 **方法 1** ：樸素遞歸方法。 **方法**：樸素的方法是從第一個元素開始，然后遞歸調用從第一個元素可到達的所有元素。 可以使用從第一個可到達元素開始到達終點所需的最小跳數來計算從第一個到達終點的最小跳數。 *minJumps（開始，結束）= Min（minJumps（k，結束）），從開始就可以到達所有 k* ## C++ ```cpp // C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the minimum number // of jumps to reach arr[h] from arr[l] int minJumps(int arr[], int n) { ????// Base case: when source and ????// destination are same ????if (n == 1) ????????return 0; ????// Traverse through all the points ????// reachable from arr[l] ????// Recursivel, get the minimum number ????// of jumps needed to reach arr[h] from ????// these reachable points ????int res = INT_MAX; ????for (int i = n - 2; i >= 0; i--) { ????????if (i + arr[i] >= n - 1) { ????????????int sub_res = minJumps(arr, i + 1); ????????????if (sub_res != INT_MAX) ????????????????res = min(res, sub_res + 1); ????????} ????} ????return res; } // Driver Code int main() { ????int arr[] = { 1, 3, 6, 3, 2, ??????????????????3, 6, 8, 9, 5 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << "Minimum number of jumps to"; ????cout << " reach the end is " << minJumps(arr, n); ????return 0; } // This code is contributed // by Shivi_Aggarwal ```