C++で配列の末尾に到達するジャンプ経路の数を数える方法

正の整数からなる配列が与えられます。各要素は、そのインデックスから配列の末尾に到達するために一度に進める最大ステップ数（最大ジャンプ長）を表します。この記事では、各要素から出発したときに配列の末尾へ到達できるジャンプ経路の数を求める方法を解説します。

たとえば arr[] = {1, 2, 3} の場合、「1」からは 1 ステップのジャンプが 1 通り、「2」からは 1 または 2 ステップのジャンプが可能ですが、末尾に届くのは 1 ステップのときだけです。「3」はすでに末尾にあるため、追加のジャンプは不要です。

入力

arr[] = {1,2,3}

出力

末尾に到達するジャンプ方法の数: 1 1 0

説明

「1」のジャンプ: 1 通り。
「2」のジャンプ: 1 または 2。ただし末尾に到達するには 1 ジャンプで十分。
「3」のジャンプ: 1、2、3 のいずれか。すでに末尾のためジャンプは不要（0）。

入力

arr[] = {4,3,6,2}

出力

末尾に到達するジャンプ方法の数: 4 2 1 0

説明

「4」のジャンプ: 1、2、3、4。末尾に届くのは 1、2、3 のいずれか。経路は 4→3→6→2、4→6→2、4→2、4→3→2 の合計 4 通り。
「3」のジャンプ: 1、2、3。経路は 3→6→2、3→2 の合計 2 通り。
「6」のジャンプ: 1〜5。末尾に届くには 1。経路は 6→2 の 1 通り。
「2」のジャンプ: 1 または 2。すでに末尾のためジャンプは不要（0）。

アルゴリズムの考え方

このアプローチでは、各要素 arr[i] について、現在の要素から到達できる前方の各要素における「末尾への到達方法の数」を合計します。さらに、arr[i] から 1 回のジャンプで直接末尾に届く場合は、その分として 1 を加算します。これは配列を右から左へ処理する動的計画法（DP）の一種です。

• 整数配列 arr[] を用意します。
• 関数 reach_end(int arr[], int size) は配列を受け取り、末尾に到達するジャンプ方法の数を出力します。
• arr[] の各要素から末尾への到達方法の数を格納するための配列 arr_2[] を用意します。
• memset(arr_2, 0, sizeof(arr_2)) で arr_2[] 全体を 0 に初期化します。
• 最後の要素は対象外のため、for ループで i = size−2 から i = 0 まで逆順に走査します。
• temp = size − i − 1（末尾までの距離）とします。arr[i] >= temp であれば 1 回のジャンプで直接末尾に届くため、arr_2[i]++ でカウントを 1 増やします。
• 続いて、arr[i] から到達可能で、かつ末尾へ到達できる他の要素の方法の数を arr_2[i] に加算します。
• そのため、j = i+1 から j < size−1 かつ j <= arr[i]+i の範囲で for ループを実行し、arr_2[j] が −1 でない（末尾に到達できる）場合はその値を arr_2[i] に足します。
• 最後まで arr_2[i] が 0 のままなら −1 を設定します。これは末尾に到達できないことを意味します。
• すべてのループが完了すると、arr_2[] には arr[] の各要素から末尾への到達方法の数が格納されています。
• for ループで arr_2[] の内容を結果として出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
void reach_end(int arr[], int size){
    int arr_2[size];
    memset(arr_2, 0, sizeof(arr_2));
    for (int i = size−2; i >= 0; i−−){
        int temp = size − i − 1;
        if (arr[i] >= temp){
            arr_2[i]++;
        }
        for (int j = i+1; j < size−1 && j <= arr[i] + i; j++){
            if (arr_2[j] != −1){
                arr_2[i] = arr_2[i] + arr_2[j];
            }
        }
        if(arr_2[i] == 0){
            arr_2[i] = −1;
        }
    }
    cout<<"Count of number of ways to jump to reach end are: ";
    for (int i=0; i < size; i++){
        cout<<arr_2[i] << " ";
    }
}
int main(){
    int arr[] = {2, 3, 7, 1, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    reach_end(arr, size);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

Count of number of ways to jump to reach end are: 8 5 3 1 1 0

計算量

外側のループが配列全体を走査し、内側のループが最大で arr[i] ステップ先まで確認するため、時間計算量は最悪で O(n²) となります。また、各要素の到達方法の数を保存するため、空間計算量は O(n) です。