C++で解く「ジャンプゲームV」：メモ化再帰による最大訪問インデックス数の求め方

問題の概要

整数型の配列 arr と整数 d が与えられます。1ステップごとに、インデックス i から次の場所へジャンプできます。

• 右方向： i + x（ただし i + x < n、かつ x は 1 以上 d 以下）
• 左方向： i - x（ただし i - x >= 0、かつ x は 1 以上 d 以下）

ここで n は配列のサイズです。さらに重要な制約として、インデックス i から j へジャンプできるのは、arr[i] > arr[j] であり、かつ i と j の間にあるすべてのインデックス k に対して arr[i] > arr[k] を満たす場合のみです。つまり、より低い位置へジャンプするとき、その経路上に自分より高い値があってはなりません。

配列内の任意のインデックスからスタートでき、訪問できるインデックス数の最大値を求めるのがこの問題の目的です。

入力例と出力

例として、d = 2、配列の高さが次のような場合を考えます。

{6, 4, 14, 6, 8, 13, 9, 7, 10, 6, 12}

このとき出力は 4 になります。インデックス 10（値 10）からスタートし、「10 → 8 → 6 → 7」の順にジャンプできるためです。仮にインデックス 6（値 13）から始めた場合は、インデックス 7（値 9）へしか移動できません。インデックス 5（値 9）には移動できません。なぜなら間のインデックス 6 の値 13 が 9 より大きいからです。同様に、インデックス 3 からインデックス 2 や 1 へのジャンプも不可能です。

解法のアプローチ：メモ化再帰（動的計画法）

この問題は、各インデックスから到達できる最大ステップ数を記録しておくメモ化（メモイゼーション）付き再帰で効率的に解けます。手順は以下の通りです。

1. 結果をキャッシュするための配列 dp を用意します。
2. 関数 solve(arr, idx, d) を定義します。
3. dp[idx] が -1 以外（計算済み）であれば、その値をそのまま返します。
4. 初期値 ret := 1（自分自身を含む最低1インデックス）とします。
5. n := arr のサイズとします。
6. 右方向への探索： i := idx + 1 から n - 1 までループします。
   • i > idx + d になったらループを抜ける（ジャンプ距離の上限）。
   • arr[i] >= arr[idx] になったらループを抜ける（それより先はジャンプ不可）。
   • ret := max(ret, 1 + solve(arr, i, d)) で最大値を更新。
7. 左方向への探索： i := idx - 1 から 0 まで同様にループします。
   • i < idx - d になったらループを抜ける。
   • arr[i] >= arr[idx] になったらループを抜ける。
   • ret := max(ret, 1 + solve(arr, i, d)) で最大値を更新。
8. dp[idx] := ret を保存して返します。

メイン処理では、すべての開始地点について solve() を呼び出し、その最大値を答えとします。

C++実装例

以下が実際の実装コードです。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    vector<int> dp;
    int solve(vector <int>& arr, int idx, int d){
       if (dp[idx] != -1)
       return dp[idx];
       int ret = 1;
       int n = arr.size();
       for (int i = idx + 1; i < n; i++) {
          if (i > idx + d)
          break;
          if (arr[i] >= arr[idx])
          break;
          ret = max(ret, 1 + solve(arr, i, d));
       }
       for (int i = idx - 1; i >= 0; i--) {
          if (i < idx - d)
          break;
          if (arr[i] >= arr[idx])
          break;
          ret = max(ret, 1 + solve(arr, i, d));
       }
       return dp[idx] = ret;
    }
    int maxJumps(vector<int>& arr, int d) {
       int n = arr.size();
       dp = vector<int>(n, -1);
       int ret = 1;
       for (int i = 0; i < n; i++) {
          ret = max(ret, solve(arr, i, d));
       }
       return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {6,4,14,6,8,13,9,7,10,6,12};
    cout << (ob.maxJumps(v, 2));
}

入力

{6,4,14,6,8,13,9,7,10,6,12}, 2

出力

4

計算量について

各インデックスの結果は一度だけ計算され、以降はキャッシュされた値を参照するため、時間計算量は O(n × d)、空間計算量は O(n) となります。素朴な全探索では指数時間になり得るところを、メモ化によって大幅に高速化できるのがこの手法のポイントです。