Minimum Number of Jumps to Reach End

กำหนดอาร์เรย์ของจำนวนเต็มบวก แต่ละค่าแทน จำนวนก้าวสูงสุด ที่เดินได้จากตำแหน่งนั้น ต้องการหา จำนวนครั้งน้อยที่สุด ในการกระโดดจาก index 0 ไปยัง index n-1

ตัวอย่าง Input และ Output

Input: {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: Minimum number of jumps to reach end is: 3

เส้นทาง: index 0(값 1) → index 1(값 3) → index 4(값 9) → index 10 (end)
Jump 1: 0→1 (1 step)
Jump 2: 1→4 (3 steps)
Jump 3: 4→10 (9 steps, overshoot OK)

อัลกอริทึม Dynamic Programming

ฟังก์ชัน minPossibleJump(list, n)

กำหนด:

jumps[i] = จำนวนครั้งน้อยที่สุดในการกระโดดจาก index 0 ไป index i

Recurrence:

jumps[i] = min(jumps[j] + 1) สำหรับทุก j ที่ j + list[j] >= i (กระโดดจาก j ถึง i ได้)

ขั้นตอน:

1. ถ้า n=0 หรือ list[0]=0 → ไม่สามารถเดินทางได้ (คืน INF)
2. jumps[0] = 0
3. for i = 1 ถึง n-1:
   • jumps[i] = INF
   • for j = 0 ถึง i-1:
     • ถ้า i <= j + list[j] และ jumps[j] != INF:
     • jumps[i] = min(jumps[i], jumps[j] + 1)
     • break (เพราะ j เรียงจากน้อยไปมาก จะได้ค่าต่ำสุดเร็วที่สุด)
4. คืน jumps[n-1]

ตัวอย่างโค้ด C++

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int minPossibleJump(int list[], int n) {
    int *jumps = new int[n];
    if (n == 0 || list[0] == 0) return INT_MAX;
    
    jumps[0] = 0;
    for (int i = 1; i < n; i++) {
        jumps[i] = INT_MAX;
        for (int j = 0; j < i; j++) {
            if (i <= j + list[j] && jumps[j] != INT_MAX) {
                jumps[i] = min(jumps[i], jumps[j] + 1);
                break; // optimization: first valid j gives minimum
            }
        }
    }
    int result = jumps[n-1];
    delete[] jumps;
    return result;
}

int main() {
    int list[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
    int size = 11;
    cout << "Minimum number of jumps to reach end is: " 
         << minPossibleJump(list, size);
    return 0;
}

Output

Minimum number of jumps to reach end is: 3

ความซับซ้อน

• Time: O(n²) (แต่ด้วย break เร็วกว่านี้)
• Space: O(n)

วิธี Greedy O(n) (Optimal)

int minJumpsGreedy(int arr[], int n) {
    if (n <= 1) return 0;
    if (arr[0] == 0) return -1;
    
    int maxReach = arr[0], step = arr[0], jump = 1;
    for (int i = 1; i < n; i++) {
        if (i == n-1) return jump;
        maxReach = max(maxReach, i + arr[i]);
        step--;
        if (step == 0) {
            jump++;
            if (i >= maxReach) return -1;
            step = maxReach - i;
        }
    }
    return -1;
}

Greedy ทำงานได้เพราะเราต้องการแค่จำนวนครั้ง ไม่ต้องการเส้นทางจริง