Chúng tôi đã cho, một mảng các số nguyên không âm biểu thị số bước tối đa có thể được thực hiện từ phần tử đó. Con trỏ ban đầu được định vị tại chỉ mục đầu tiên [0 chỉ mục] của mảng. Mục tiêu của bạn là đạt được lastindex của mảng với số bước tối thiểu. Nếu không thể đến phần cuối của mảng, hãy in số nguyên tối đa.
cách tiếp cận ngây thơ là bắt đầu từ thành phần ban đầu {the primary} và gọi đệ quy cho tất cả các thành phần có thể truy cập được từ phần tử đầu tiên. Phạm vi tối thiểu của bước nhảy để đạt được kết thúc từ đầu tiên được tính bằng cách sử dụng phạm vi nhảy tối thiểu cần thiết để đạt được kết thúc từ các phần tử có thể truy cập từ đầu tiên.
minJumps(start, end) = Min ( minJumps(k, end) ) for all k accessible from the start
Ở đây, chúng tôi sẽ sử dụng cách tiếp cận từ trên xuống của lập trình động. Chúng tôi sẽ sử dụng Hashmap để lưu trữ kết quả vấn đề con và bất cứ khi nào chúng tôi tạo giải pháp, trước tiên hãy kiểm tra xem vấn đề con đã được giải quyết chưa, nếu có thì hãy sử dụng nó.
Input: { 1, 2, 4, 1, 2, 2, 1, 1, 3, 8 }
Output: Minimum number of steps = 6 {1-->2-->4-->1-->3-->8} Giải thích
Phần tử đầu tiên là 1, vì vậy nó chỉ có thể đi đến 2. Phần tử thứ hai là 2, do đó, có thể thực hiện nhiều nhất 2 bước, ví dụ đến 4 hoặc 1. Nó đi đến 4 từ nơi nó đến 1 và tiếp tục.
Độ phức tạp của phương pháp lập trình động để tìm số lần nhảy nhỏ nhất để đến cuối một mảng là O (n ^ 2) với độ phức tạp không gian là O (n)
Ví dụ
#include<stdio.h>
#include<limits.h>
int min_steps (int arr[], int n){
int steps[n];
int i, j;
if (n == 0 || arr[0] == 0)
return INT_MAX;
steps[0] = 0;
for (i = 1; i < n; i++){
steps[i] = INT_MAX;
for (j = 0; j < i; j++){
if (i <= j + arr[j] && steps[j] != INT_MAX){
steps[i] = (steps[i] < (steps[j] + 1)) ? steps[i] : steps[j] + 1;
break;
}
}
}
return steps[n - 1];
}
int main (){
int arr[100];
int n;
printf ("Enter size of the array:");
scanf ("%d", &n);
printf ("Enter elements in the array:");
for (int i = 0; i < n; i++){
scanf ("%d", &arr[i]);
}
printf ("Minimum number of steps : %d", min_steps (arr, n));
return 0;
} Đầu ra
Enter size of array : 7 Enter elements in the array :2 1 1 5 2 1 1 Minimum number of steps : 3