C++で解く「交差しない接続線」問題:動的計画法で最大本数を求める方法

問題概要

2つの整数配列 A と B が与えられ、それぞれ別々の水平な直線上に、与えられた順序どおりに並べて書かれているとします。ここで、次の条件を満たす「接続線」を引くことを考えます。

• A[i] == B[j] を満たす2つの数 A[i] と B[j] を結ぶこと

• 引いた線が、他のどの接続線(水平線は除く)とも一切交差しないこと

重要なのは、接続線どうしは端点同士でも接触してはいけないという点です。つまり、1つの数値が属せる接続線は高々1本だけです。この条件下で、引くことのできる接続線の最大本数を求めます。

たとえば、入力が [1,4,2] と [1,2,4] の場合、答えは 2 になります。

上の表のように、2本の交差しない線を引くことは可能です。しかし3本は引けません。A[1]=4 から B[2]=4 への線と、A[2]=2 から B[1]=2 への線が交差してしまうためです。

解法の考え方

実はこの問題は、「最長共通部分列(LCS)」とまったく同じ構造をしています。A と B の共通する要素を、順序を保ったまま選ぶことができれば、その選び方がそのまま交差しない接続線に対応するからです。そこで、再帰呼び出しとメモ化(動的計画法)を組み合わせて解きます。手順は以下のとおりです。

• solve() というメソッドを定義します。引数は添字 i、j、配列 A、配列 B、およびメモ化用の行列 dp です。

• i が配列 A の範囲外であれば 0 を返します。

• j が配列 B の範囲外であれば 0 を返します。

• nj := j と初期化します。

• nj が B のサイズ未満であり、かつ B[nj] != A[i] である間、nj を1ずつ増やします(A[i] と一致する位置を探します)。

• nj が B のサイズ未満なら temp := 1、そうでなければ temp := 0 とします。

• ret := max(solve(i+1, j, A, B, dp), temp + solve(i+1, nj+1, A, B, dp)) とします。「A[i] を使わない場合」と「A[i] を B[nj] と結ぶ場合」のうち良い方を選んでいます。

• dp[i][j] := ret として結果を保存し、ret を返します。

• メインのメソッドからは次を行います。

  • n := A のサイズ、m := B のサイズ とする

  • n × m の行列 dp を作成し、すべて −1 で初期化する(未計算の印)

  • solve(0, 0, A, B, dp) を呼び出して結果を得る

C++での実装例

以下に実際のコードを示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(int i, int j, vector<int>& A, vector<int>& B, vector<vector<int>>& dp){
        if(i >= A.size()) return 0;
        if(j >= B.size()) return 0;
        if(dp[i][j] != -1) return dp[i][j];
        int nj = j;
        while(nj < B.size() && B[nj] != A[i]) nj++;
        int ret = max(solve(i + 1, j, A, B, dp), (nj < B.size() ? 1 : 0) + solve(i + 1, nj + 1, A, B, dp));
        return dp[i][j] = ret;
    }
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        int n = A.size();
        int m = B.size();
        vector<vector<int>> dp(n, vector<int>(m, -1));
        return solve(0, 0, A, B, dp);
    }
};
main(){
    vector<int> v1 = {1,4,2};
    vector<int> v2 = {1,2,4};
    Solution ob;
    cout << (ob.maxUncrossedLines(v1, v2));
}

入力

[1,4,2]
[1,2,4]

出力

2

計算量と補足

状態 (i, j) の組は高々 n × m 通りしか存在せず、各状態の結果は dp テーブルにキャッシュされるため、このアルゴリズムの時間計算量は O(n × m)、空間計算量も O(n × m) となります。なお、この問題は前述のとおり最長共通部分列(LCS)の長さを求める問題と等価なので、ボトムアップ型のDPで書き換えることもできます。その場合、dp[i][j] を「A の先頭 i 要素と B の先頭 j 要素を使ったときの答え」と定義し、A[i-1] == B[j-1] なら dp[i-1][j-1] + 1、そうでなければ max(dp[i-1][j], dp[i][j-1]) と漸化式を立てれば、再帰なしで同様の結果が得られます。