配列の末尾に到達するための最小ジャンプ回数を求めるCプログラム

問題の概要

非負整数の配列が与えられ、各要素はその位置から前方へ進むことができる最大ステップ数を表しています。ポインタは初期状態で配列の先頭（インデックス0）に配置されています。目標は、最小のジャンプ回数で配列の最後のインデックスに到達することです。もし配列の末尾に到達することが不可能な場合は、整数型の最大値（INT_MAX）を出力します。

ナイーブなアプローチ（全探索）

最も単純な方法は、最初の要素から出発し、そこから到達可能なすべての要素に対して再帰的に処理を呼び出すことです。先頭から末尾に到達するまでの最小ジャンプ数は、「最初の要素から到達できる各要素から末尾までに必要な最小ジャンプ数」の中で最も小さい値を取ることで求められます。

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

動的計画法（トップダウンアプローチ）

ここでは動的計画法のトップダウンアプローチを活用します。ハッシュマップを使って部分問題の計算結果を保存しておき、新しい解を求める際には、まずその部分問題がすでに解決済みかどうかを確認します。解決済みであれば、保存された結果を再利用することで、無駄な再計算を避けることができます。

入力: { 1, 2, 4, 1, 2, 2, 1, 1, 3, 8 }
出力: 最小ステップ数 = 6 {1-->2-->4-->1-->3-->8}

動作の解説

最初の要素は「1」なので、次に進めるのは「2」の位置だけです。2番目の要素は「2」なので、最大2ステップ進むことができ、「4」または「1」の位置へ移動可能です。ここでは「4」へ進み、そこからさらに「1」へ、というように順番に末尾を目指します。

この動的計画法によるアプローチの時間計算量は O(n²)、空間計算量は 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

このように、動的計画法を用いることで、配列の各位置に到達するための最小ジャンプ回数を効率的に計算できます。到達不可能な場合には INT_MAX が返されるため、呼び出し側で適切に判定することが可能です。