C#で配列の末尾に到達するために必要な最小ジャンプ回数を求める方法

この問題は、配列の先頭要素からスタートし、そこから到達可能なすべての要素に対して再帰的に同じ処理を呼び出すことで解くことができます。先頭から配列の末尾に到達するまでの最小ジャンプ回数は、「先頭から到達可能な各要素から末尾へ到達するのに必要な最小ジャンプ回数」をもとにして計算できます。

例として、次の配列を考えてみましょう。

Array == {1, 3, 6, 3, 2, 3, 6, 8, 9, 5};

この場合、末尾に到達するために必要なジャンプ回数は 4 回 です。

アルゴリズムの考え方

現在位置にある値が「その位置から何歩先までジャンプできるか」を表しています。そこで、ジャンプ可能な範囲内の各候補地点について、それぞれからゴール（配列の末尾）までの最小ジャンプ回数を再帰的に求めます。得られた結果に 1 を加えた値のうち最も小さいものが、現在位置からの答えになります。

なお、現在位置の値が 0 の場合はそれ以上前に進めないため、到達不可能を意味する int.MaxValue を返します。

実装例

using System;
namespace ConsoleApplication{
    public class Arrays{
        public int MinJumps(int[] arr, int l, int h){
            if (h == l)
                return 0;
            if (arr[l] == 0)
                return int.MaxValue;
            int min = int.MaxValue;
            for (int i = l + 1; i <= h && i <= l + arr[l]; i++){
                int jumps = MinJumps(arr, i, h);
                if (jumps != int.MaxValue && jumps + 1 < min)
                    min = jumps + 1;
            }
            return min;
        }
    }
    class Program{
        static void Main(string[] args){
            Arrays a = new Arrays();
            int[] arrm = { 1, 3, 6, 3, 2, 3, 6, 8, 9, 5 };
            int n = arrm.Length;
            Console.Write(" Minimum number of jumps to reach end is " + a.MinJumps(arrm, 0, n - 1));
        }
    }
}

出力

4

計算量について

この素朴な再帰アプローチでは、各位置から複数の経路を重複して探索するため、最悪の場合の時間計算量は指数関数的になります。実際の開発では、メモ化（キャッシュ）や動的計画法を組み合わせることで、O(n²) 程度まで効率化できる点に注意してください。