ให้อาร์เรย์จำนวนเต็มไม่ติดลบ แสดงจำนวนขั้นตอนสูงสุดที่ก้าวไปข้างหน้าได้จากตำแหน่งนั้น เริ่มต้นที่ดัชนี 0 เป้าหมาย: ถึงดัชนีสุดท้ายในขั้นตอนน้อยที่สุด ถ้าไม่ถึงได้ พิมพ์ค่าสูงสุดของ int
Naive approach เริ่มจากสมาชิกแรก เรียกเวียน (recursive) สำหรับทุกสมาชิกที่เข้าถึงได้ minJumps(start, end) = Min(minJumps(k, end)) สำหรับ k ทุกตัวที่เข้าถึงได้จาก start
ใช้ Dynamic Programming แบบ Top-down ใช้ Hashmap เก็บผลลัพธ์ subproblem
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 ...
Complexity: O(n²) time, O(n) space
ตัวอย่างโค้ด
#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
