C程式尋找到達末尾的最小跳數

給定一個非負整數數組，表示最大數量 可以從該元素向前邁出的步驟。指標最初位於數組的第一個索引 [0 索引] 處。你的目標是到達最後 最少步數中數組的索引。如果無法到達 數組末尾，然後列印最大整數。

天真的方法是從初始{主要}元件開始，並遞歸呼叫可從第一個元素存取的所有元件。從第一個到達末尾的最小跳躍範圍是使用從第一個可訪問的元素到達末尾所需的最小跳躍範圍來計算的。

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

以上是C程式尋找到達末尾的最小跳數的詳細內容。更多資訊請關注PHP中文網其他相關文章！