C++で解くコインパス問題：最小コストのジャンプ経路を求める動的計画法

問題の概要

N個の数値 A1, A2, ..., AN を含む配列A（インデックスは1から開始）と、整数Bが与えられます。整数Bは、配列Aの任意のインデックスiから、i+1、i+2、…、i+B のいずれかの位置へジャンプできることを意味します。ただし、インデックスiに着地するには Ai 枚のコインを支払う必要があり、Ai が -1 の場合、その位置にはジャンプできません。

配列Aのインデックス1から出発し、できるだけ少ないコインでインデックスNに到達することが目的です。最小コストでゴールへたどり着くためのインデックスの経路（1からN）を返してください。同じコストの経路が複数存在する場合は、辞書順で最も小さい経路を選びます。ゴールに到達する経路が存在しない場合は、空の配列を返します。

入力例： [1,2,4,-1,2], B=2 の場合、出力は [1,3,5] になります。

解き方の考え方

この問題は動的計画法（DP）を使うことで効率的に解けます。ゴール側（配列の末尾）から逆方向に計算し、「位置iからゴールまで進むための最小コスト」と「そのとき次にジャンプすべき位置」を記録していきます。こうすることで、スタート地点から記録したリンクをたどるだけで最適な経路を復元できます。

具体的な手順は以下の通りです。

• n := 配列Aのサイズとする

• 結果を格納する配列 ret を定義する

• サイズnの配列 cost を定義し、すべて無限大（inf）で初期化する

• サイズnの配列 next を定義し、すべて -1 で初期化する

• n が 0、または A[n - 1] が -1 の場合は −

  • 空の配列を返す

• endPoint := n - 1 とする

• cost[n - 1] = A[n - 1] とする

• i を n - 2 から 0 まで 1 ずつ減らしながら、以下を繰り返す −

  • A[i] が -1 の場合は −

    • 以降をスキップして次の反復へ進む

  • j を i + 1 から min(n - 1, i + B) まで 1 ずつ増やしながら、以下を繰り返す −

    • cost[j] + A[i] < cost[i] である場合 −

      • cost[i] := cost[j] + A[i]

      • next[i] := j

      • endPoint := i

• endPoint が 0 と等しくない場合は −

  • 空の配列を返す

• endPoint が -1 になるまで、endPoint = next[endPoint] と更新しながら、以下を繰り返す −

  • ret の末尾に endPoint + 1 を追加する

• ret を返す

ここでのポイントは、内側のループで j を小さい方から走査し、更新条件を「より小さい（<）」に限定している点です。これにより、コストが同額になる選択肢がある場合には常に小さいインデックス側が優先され、結果として辞書順最小の経路が得られます。

入力例 [1,2,4,-1,2], B=2 では、インデックス1（コスト1）からインデックス3（コスト4）へジャンプし、さらにインデックス5（コスト2）へ進みます。合計コストは 1 + 4 + 2 = 7 となり、これが最小です。-1 の位置（インデックス4）には着地できない点に注意してください。

C++実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector<int> cheapestJump(vector<int>& A, int B) {
        int n = A.size();
        vector <int> ret;
        vector <int> cost(n, 1e9);
        vector <int> next(n, -1);
        if(!n || A[n - 1] == -1) return {};
        int endPoint = n - 1;
        cost[n - 1] = A[n - 1];
        for(int i = n - 2; i >= 0; i--){
            if(A[i] == -1) continue;
            for(int j = i + 1 ; j <= min(n - 1, i + B); j++){
                if(cost[j] + A[i] < cost[i]){
                    cost[i] = cost[j] + A[i];
                    next[i] = j;
                    endPoint = i;
                }
            }
        }
        if(endPoint != 0) return {};
        for(;endPoint != - 1; endPoint = next[endPoint]){
            ret.push_back(endPoint + 1);
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,4,-1,2};
    print_vector(ob.cheapestJump(v, 2));
}

入力

{1,2,4,-1,2}, 2

出力

[1, 3, 5]

計算量

時間計算量は O(N×B)、空間計算量は O(N) です。各位置について最大B個のジャンプ先を調べるため、配列の長さとジャンプ幅の積に比例した処理時間で動作します。