เราได้รับอาร์เรย์ของจำนวนเต็มที่ไม่ติดลบซึ่งแสดงถึงจำนวนขั้นตอนสูงสุดที่สามารถทำต่อจากองค์ประกอบนั้นได้ ตัวชี้อยู่ในตำแหน่งเริ่มต้นที่ดัชนีแรก [ดัชนี 0 รายการ] ของอาร์เรย์ เป้าหมายของคุณคือการเข้าถึงดัชนีสุดท้ายของอาร์เรย์ในจำนวนขั้นตอนขั้นต่ำ หากไปถึงจุดสิ้นสุดของอาร์เรย์ไม่ได้ ให้พิมพ์จำนวนเต็มสูงสุด
แนวทางไร้เดียงสา คือการเริ่มต้นจากองค์ประกอบเริ่มต้น {the primary} และเรียกซ้ำสำหรับส่วนประกอบทั้งหมดที่สามารถเข้าถึงได้จากองค์ประกอบแรก ช่วงการกระโดดขั้นต่ำเพื่อไปให้ถึงจุดสิ้นสุดจากช่วงแรกคำนวณโดยใช้ช่วงกระโดดขั้นต่ำที่จำเป็นเพื่อให้ได้จุดสิ้นสุดจากองค์ประกอบที่เข้าถึงได้ตั้งแต่ช่วงแรก
minJumps(start, end) = Min ( minJumps(k, end) ) for all k accessible from the start
เราจะใช้วิธีการเขียนโปรแกรมแบบไดนามิกจากบนลงล่าง เราจะใช้ Hashmap เพื่อเก็บผลลัพธ์ของปัญหาย่อย และเมื่อใดก็ตามที่เราสร้างโซลูชัน ก่อนอื่นให้ตรวจสอบว่าปัญหาย่อยได้รับการแก้ไขแล้วหรือไม่ ถ้าใช่ ให้ใช้มัน
Input: { 1, 2, 4, 1, 2, 2, 1, 1, 3, 8 }
Output: Minimum number of steps = 6 {1-->2-->4-->1-->3-->8} คำอธิบาย
องค์ประกอบแรกคือ 1 จึงไปได้เพียง 2 องค์ประกอบที่สองคือ 2 จึงทำได้สูงสุด 2 ขั้นตอน เช่น 4 หรือ 1 ไปถึง 4 จากจุดที่ 1 เป็นต้น
ความซับซ้อนของวิธีการเขียนโปรแกรมไดนามิกในการหาจำนวนการข้ามขั้นต่ำเพื่อไปให้ถึงจุดสิ้นสุดของอาร์เรย์คือ O(n^2) โดยมีค่าความซับซ้อนของพื้นที่เป็น O(n)
ตัวอย่าง
#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;
} ผลลัพธ์
Enter size of array : 7 Enter elements in the array :2 1 1 5 2 1 1 Minimum number of steps : 3
