終わりに到達するためのジャンプの最小数のためのCプログラム

その要素から前進できる最大ステップ数を示す非負の整数の配列が与えられます。ポインタは、最初は配列の最初のインデックス[0インデックス]に配置されます。あなたの目標は、最小のステップ数で配列のlastindexに到達することです。配列の最後に到達できない場合は、最大整数を出力します。

素朴なアプローチ initial {primary}コンポーネントから開始し、最初の要素からアクセス可能なすべてのコンポーネントを再帰的に呼び出します。最初から最後まで到達するためのジャンプの最小範囲は、最初からアクセス可能な要素から終了を達成するために必要なジャンプの最小範囲を使用して計算されます。

minJumps(start, end) = Min ( minJumps(k, end) )
for all k accessible from the start

ここでは、動的計画法のトップダウンアプローチを使用します。ハッシュマップを使用してサブ問題の結果を保存します。ソリューションを作成するときは常に、最初にサブ問題がすでに解決されているかどうかを確認し、解決されている場合はそれを使用します。

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なので、最大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