ジャンプの最小回数問題を動的計画法で解く方法

この問題では、正の整数からなるリストが与えられます。各整数は、その位置から最大で何ステップ先へ進めるかを表しています。最初の要素から出発し、リストの末尾の要素に到達するまでに必要な最小ジャンプ回数を求めます。

動的計画法（DP）によるアプローチでは、最小ジャンプ回数を保存するための jumps 配列を定義します。たとえば jumps[i] には、配列のインデックス 0 からインデックス i に到達するまでに必要な最小ジャンプ回数が記録されます。

入力と出力

入力:
整数のリスト {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
出力:
末尾の位置に到達するための最小ジャンプ回数。この場合は 3。
値 1 の位置からスタートして 3 へ移動し、さらにジャンプして 8 に到達。
最後に 8 の位置からジャンプして、リストの最後の要素へたどり着きます。

アルゴリズム

手続き minPossibleJump(list, n) の流れは次のとおりです。

minPossibleJump(list, n)

入力： 数値の配列、および配列の要素数。

出力： 配列の末尾に到達するために必要な最小ジャンプ回数。

Begin
    define an array named jump of size n
    if n = 0 or list[0] = 0, then
        return ∞
    jump[0] := 0

    for i := 1 to n, do
        jumps[i] := ∞
        for j := 0 to i, do
            if i <= j + list[j] and jump[j] ≠ ∞, then
                jump[i] := minimum of jump[i] and (jump[j] + 1)
                break the loop
        done
    done

    return jump[n-1]
End

アルゴリズムのポイント

jumps[i] ははじめに無限大（INT_MAX）で初期化しておきます。そして、位置 j から位置 i へ届く場合（j + list[j] ≥ i）、かつ jumps[j] が到達可能な値である場合にのみ、jumps[i] を jumps[j] + 1 で更新します。これにより、最終的な jumps[n-1] がスタートからゴールまでの最小ジャンプ回数となります。jumps[n-1] が無限大のままの場合は、ゴールに到達できないことを意味します。

実装例（C++）

#include<iostream>
using namespace std;

int min(int x, int y) {
    return (x < y)? x: y;
}

int minPossibleJump(int list[], int n) {
    int *jumps = new int[n];      // ジャンプ回数を保存する jumps 配列を動的に確保
    if (n == 0 || list[0] == 0)
        return INT_MAX;
    jumps[0] = 0;

    for (int i = 1; i < n; i++) {
        jumps[i] = INT_MAX;       // はじめにすべてのジャンプ回数を無限大として設定
        for (int j = 0; j < i; j++) {
            if (i <= j + list[j] && jumps[j] != INT_MAX) {
                jumps[i] = min(jumps[i], jumps[j] + 1);
                break;
            }
        }
    }
    return jumps[n-1];
}

int main() {
    int list[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
    int size = 11;
    cout << "Minimum number of jumps to reach end is: "<< minPossibleJump(list,size);
    return 0;
}

出力

Minimum number of jumps to reach end is: 3

計算量

このアルゴリズムは、各インデックス i についてそれより前のすべての位置 j を調べるため、時間計算量は O(n²) です。また、結果を保存する jumps 配列が必要となるため、補助記憶域の計算量は O(n) となります。