C++で最長フィボナッチ型部分列の長さを求める方法

問題概要

数列 X₁, X₂, ..., X_n が「フィボナッチ型」であるとは、次の条件を満たすことを指します。

• n >= 3 である
• すべての i + 2 <= n に対して、X_i + X_i+1 = X_i+2 が成り立つ

ここで、正整数からなる狭義単調増加配列 A が与えられたとき、A の中に含まれる最も長いフィボナッチ型部分列の長さを求めます。該当する部分列が存在しない場合は 0 を返します。

たとえば、配列が [1,2,3,4,5,6,7,8] の場合、答えは 5 になります。このとき最も長いフィボナッチ型部分列は [1,2,3,5,8] です。

解法アプローチ：動的計画法(DP)

この問題は動的計画法を用いることで効率的に解けます。dp[i][j] を「部分列の末尾2要素が A[j]、A[i] であるようなフィボナッチ型部分列の長さ」と定義します。さらに、ハッシュマップで各値のインデックスを管理しておけば、直前の要素が必要かどうかを O(1) で判定できます。

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

• ret := 0 で初期化する
• マップ m を作成し、n := 配列 A のサイズとする
• n × n のサイズを持つ二次元配列 dp を作成する
• i を 0 から n − 1 まで繰り返す
  • m[A[i]] := i を設定する
  • j を i − 1 から 0 まで降順に繰り返す
    • req := A[i] − A[j] を計算する
    • A[i] − A[j] < A[j] かつマップ m に A[i] − A[j] が存在する場合
      • dp[i][j] := max(dp[i][j], dp[j][m[A[i] − A[j]]] + 1)
    • それ以外の場合は dp[i][j] := max(dp[i][j], 2) とする
    • ret := max(ret, dp[i][j]) で最大値を更新する
• 最後に、ret >= 3 なら ret を返し、そうでなければ 0 を返す

条件「A[i] − A[j] < A[j]」により、直前の要素が必ず現在より小さい値になることが保証され、増加列として成立する組み合わせだけを効率よく探索できます。計算量は時間・空間ともに O(n²) です。

C++実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int lenLongestFibSubseq(vector<int> & A) {
      int ret = 0;
      unordered_map <int, int> m;
      int n = A.size();
      vector < vector <int> > dp(n, vector <int>(n));
      for(int i = 0; i < n; i++){
         m[A[i]] = i;
         for(int j = i - 1; j >= 0; j--){
            int req = A[i] - A[j];
            if(A[i] - A[j] < A[j] && m.count(A[i] - A[j])){
               dp[i][j] = max(dp[i][j], dp[j][m[A[i] - A[j]]] + 1);
            }else{
               dp[i][j] = max(dp[i][j], 2);
            }
            ret = max(ret, dp[i][j]);
         }
      }
      return ret >= 3 ? ret : 0;
   }
};
main(){
   vector<int> v = {1,2,3,4,5,6,7,8};
   Solution ob;
   cout << (ob.lenLongestFibSubseq(v));
}

入力

[1,2,3,4,5,6,7,8]

出力

5

まとめ

本記事では、C++を用いて配列内の最長フィボナッチ型部分列の長さを求める手法を紹介しました。DPテーブルに「末尾2要素」の情報を持たせることで、部分列の遷移を明確に追跡できるのがポイントです。同様の考え方は、等差数列や幾何数列を扱う部分列問題にも応用できるため、ぜひ覚えておきましょう。