Vấn đề về số lần nhảy tối thiểu

Trong bài toán này, một danh sách các số nguyên dương được đưa ra. Mỗi số nguyên biểu thị rằng có bao nhiêu bước tối đa có thể được thực hiện từ phần tử hiện tại. Bắt đầu từ phần tử đầu tiên, chúng ta phải tìm số lần nhảy tối thiểu để đến được mục cuối cùng của danh sách.

Đối với phương pháp lập trình động, một mảng bước nhảy được xác định để lưu trữ số bước nhảy tối thiểu cần thiết. Giống như giá trị của các bước nhảy [i], nó chỉ ra rằng cần có bao nhiêu bước nhảy tối thiểu để đạt được chỉ số thứ i của mảng từ chỉ số thứ 0.

Đầu vào và Đầu ra

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.

Thuật toán

minPossibleJump(list, n)

Đầu vào: Mảng số, số phần tử trong mảng.

Đầu ra: Số lần nhảy tối thiểu cần thiết để đạt được khi kết thúc.

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

Ví dụ

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

Đầu ra

Minimum number of jumps to reach end is: 3