จำนวนขั้นต่ำของปัญหาการกระโดด

ในปัญหานี้ จะแสดงรายการจำนวนเต็มบวก จำนวนเต็มแต่ละตัวหมายถึงจำนวนขั้นตอนสูงสุดที่สามารถทำได้จากองค์ประกอบปัจจุบัน เริ่มจากองค์ประกอบแรก เราต้องหาจำนวนการกระโดดขั้นต่ำเพื่อไปยังรายการสุดท้ายของรายการ

สำหรับแนวทางการเขียนโปรแกรมแบบไดนามิก อาร์เรย์การกระโดดถูกกำหนดให้เก็บจำนวนการข้ามขั้นต่ำที่จำเป็น เช่นเดียวกับค่าของ jumps[i] มันบ่งชี้ว่าจำเป็นต้องมีการกระโดดขั้นต่ำกี่ครั้งจึงจะไปถึงดัชนี ith ของอาร์เรย์จากดัชนีที่ 0

อินพุตและเอาต์พุต

Input:
A list of integers. {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output:
The minimum number of jumps to reach the end location. It is 3.
Start from value 1, go to 3. then jumps 3 values and reach 8. then jump 8 values and reach the last element.

อัลกอริทึม

minPossibleJump(list, n)

ป้อนข้อมูล: อาร์เรย์ตัวเลข จำนวนองค์ประกอบในอาร์เรย์

ผลลัพธ์: จำนวนการกระโดดขั้นต่ำที่ต้องไปถึงตอนท้าย

Begin
   define an array named jump of size n
   if n = 0 or list[0] = 0, then
      return ∞
   jump[0] := 0

   for i := 1 to n, do
      jumps[i] := ∞
      for j := 0 to i, do
         if i <= j + list[j] and jump[j] ≠ ∞, then
            jump[i] := minimum of jump[i] and (jump[j] + 1)
            break the loop
      done
   done

   return jump[n-1]
End

ตัวอย่าง

#include<iostream>
using namespace std;

int min(int x, int y) {
   return (x < y)? x: y;
}

int minPossibleJump(int list[], int n) {
   int *jumps = new int[n];     // dynamically create jumps array to store steps
   if (n == 0 || list[0] == 0)
       return INT_MAX;
   jumps[0] = 0;

   for (int i = 1; i < n; i++) {
      jumps[i] = INT_MAX;    //initially set jumps as infinity
      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;
         }
      }
   }
   return jumps[n-1];
}

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;
}

ผลลัพธ์

Minimum number of jumps to reach end is: 3