최대 수를 나타내는 음수가 아닌 정수 배열이 제공됩니다. 이 요소에서 앞으로 나아갈 수 있는 단계입니다. 포인터는 처음에 배열의 첫 번째 인덱스 [0 인덱스]에 위치합니다. 당신의 목표는 끝까지 도달하는 것입니다 최소 단계 수로 배열에 대한 인덱스입니다. 연결할 수 없는 경우 배열의 끝을 확인한 다음 가장 큰 정수를 인쇄합니다.
순진한 접근 방식은 초기 {main} 구성 요소부터 시작하여 첫 번째 요소에서 액세스할 수 있는 모든 구성 요소를 재귀적으로 호출하는 것입니다. 처음부터 끝까지의 최소 점프 범위는 액세스 가능한 첫 번째 요소에서 끝까지 도달하는 데 필요한 최소 점프 범위를 사용하여 계산됩니다.
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#include 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
위 내용은 끝에 도달하기 위한 최소 홉 수를 찾는 C 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
