【C++解説】steps回の移動後も同じ位置（インデックス0）にとどまる経路の数を動的計画法で求める

問題の概要

サイズ arrLen の配列があり、インデックス 0 の位置にポインタが置かれています。各ステップごとに、ポインタを左に1マス移動するか、右に1マス移動するか、その場にとどまるかのいずれかを選択できます。

ここで、整数 steps と arrLen が与えられたとき、ちょうど steps 回の操作を終えた時点でポインタが依然としてインデックス 0 に存在するような移動パターンの総数を求めます。答えが非常に大きくなる可能性があるため、10^9 + 7 で割った余りを返してください。

たとえば、入力が steps = 3、arrLen = 2 の場合、出力は 4 になります。3 ステップ後にインデックス 0 にとどまる組み合わせは次の 4 通りだからです。

• [右, 左, その場]
• [その場, 右, 左]
• [右, その場, 左]
• [その場, その場, その場]

解法のアプローチ

この問題は動的計画法（DP）によって効率的に解けます。実装の鍵となるポイントは次の 2 つです。

• 探索範囲の絞り込み： steps 回以内にインデックス 0 へ戻るには、右へ進める距離は最大でも steps / 2 マスです。したがって、考慮すべき位置は min(arrLen, steps / 2 + 1) 個だけで十分であり、無駄な計算を省けます。
• ローリング配列によるメモリ削減： i 番目の状態は直前の i − 1 番目の状態のみから導出できるため、行数 2 の 2 次元配列を使い回すことで、メモリ使用量を大幅に抑えられます。

アルゴリズムの手順

1. 定数 m を 1e9 + 7 とします。
2. 剰余演算を安全に行う関数 add(a, b) を用意します。(a mod m + b mod m) mod m を返します。
3. 再帰的な補助関数 solve(n, x, pos) を定義します（pos の初期値は 0）。
   • x が 0 の場合、pos == 0 なら true（1）、それ以外は false（0）を返します。
   • dp[pos][n] が -1 以外なら、キャッシュされた値をそのまま返します。
   • ans := 0 で初期化します。
   • pos > 0 なら、ans に solve(n, x − 1, pos − 1) を加算します（左へ移動）。
   • pos < n − 1 なら、ans に solve(n, x − 1, pos + 1) を加算します（右へ移動）。
   • さらに ans に solve(n, x − 1, pos) を加算します（その場にとどまる）。
   • dp[pos][n] := ans として結果を保存し、ans を返します。
4. メイン処理では以下を実行します。
   • x := min(arrLen, steps / 2 + 1)
   • サイズ 2 × (x + 1) の 2 次元配列 dp を 0 で初期化します。
   • dp[0][0] := 1 とします。
   • n := arrLen とします。
   • i を 1 から steps までループします。
     • j を 0 から min(arrLen, steps / 2 + 1) 未満までループします。
       • x := (i − 1) mod 2、y := i mod 2
       • dp[y][j] := dp[x][j]（その場にとどまるケース）
       • j − 1 ≥ 0 なら、dp[y][j] := add(dp[y][j], dp[x][j − 1])（左左隣から遷移）
       • j + 1 < n なら、dp[y][j] := add(dp[y][j], dp[x][j + 1])（右隣から遷移）
5. 最後に dp[steps mod 2][0] を返します。

C++での実装例

それでは、理解を深めるために実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;
lli add(lli a, lli b){
    return (a % MOD + b % MOD) % MOD;
}
class Solution {
    public:
    vector<vector<int> > dp;
    int solve(int n, int x, int pos = 0){
       if (x == 0) {
          return pos == 0;
       }
       if (dp[pos][n] != -1)
       return dp[pos][n];
       int ans = 0;
       if (pos > 0)
       ans = add(ans, solve(n, x - 1, pos - 1));
       if (pos < n - 1)
       ans = add(ans, solve(n, x - 1, pos + 1));
       ans = add(ans, solve(n, x - 1, pos));
       dp[pos][n] = ans;
       return ans;
   }
    int numWays(int steps, int arrLen){
       int x = min(arrLen, steps / 2 + 1);
       this->dp = vector<vector<int> >(2, vector<int>(x + 1, 0));
       dp[0][0] = 1;
       int n = arrLen;
       for (int i = 1; i <= steps; i++) {
          for (int j = 0; j < min(arrLen, steps / 2 + 1); j++) {
             int x = (i - 1) % 2;
             int y = i % 2;
             dp[y][j] = dp[x][j];
             if (j - 1 >= 0)
             dp[y][j] = add(dp[y][j], dp[x][j - 1]);
             if (j + 1 < n)
             dp[y][j] = add(dp[y][j], dp[x][j + 1]);
          }
       }
       return dp[steps % 2][0];
    }
};
main(){
    Solution ob;
    cout << (ob.numWays(3,2));
}

入力

3, 2

出力

4

計算量について

このボトムアップ方式の DP では、外側のループが steps 回、内側のループが最大 min(arrLen, steps / 2 + 1) 回回るため、時間計算量は O(steps × min(arrLen, steps / 2 + 1)) となります。また、使用するのは 2 行分のテーブルだけなので、空間計算量は O(min(arrLen, steps / 2 + 1)) に抑えられます。これにより、steps や arrLen が大きいケースでも高速かつ省メモリで動作します。