C 프로그램 끝에 도달하기 위한 최소 점프 횟수

해당 요소에서 앞으로 만들 수 있는 최대 단계 수를 나타내는 음이 아닌 정수 배열이 제공됩니다. 포인터는 처음에 배열의 첫 번째 인덱스 [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). 1에 도달한 곳에서 4로 가는 식입니다.

배열의 끝에 도달하기 위한 최소 점프 수를 찾기 위한 동적 프로그래밍 방식의 복잡성은 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