C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++での最長のフィボナッチサブシーケンスの長さ

シーケンスX_1、X_2、...があるとすると、-

の場合、X_nはフィボナッチのようになります。

  • n> =3

  • X_i + X_ {i + 1} =X_ {i+2}すべてのi+2 <=n

ここで、シーケンスを形成する正の整数の厳密に増加する配列Aを想定し、Aの最長のフィボナッチのようなサブシーケンスの長さを見つける必要があります。存在しない場合は0を返します。したがって、数値が[1,2 、3,4,5,6,7,8]の場合、出力は5になります。フィボナッチである最長のサブシーケンスは[1,2,3,5,8]のようになります。

これを解決するには、次の手順に従います-

理解を深めるために、次の実装を見てみましょう-

例

#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

  1. 最長共通部分列のためのC++プログラム

    サブシーケンスは、要素のセットと同じ順序のシーケンスです。シーケンス「stuv」の場合、サブシーケンスは「stu」、「tuv」、「suv」などです。 長さnの文字列の場合、文字列からサブシーケンスを作成する方法は2nあります。 例 文字列「ABCDGH」および「AEDFHR」の最長共通部分列の長さは3です。 #include <iostream> #include <string.h> using namespace std; int max(int a, int b); int lcs(char* X, char* Y, int m, int n){  

  2. Pythonで最長のフィボナッチサブシーケンスの長さを見つけるプログラム

    X_1、X_2、...のような1つのシーケンスがあるとすると、-の場合、X_nはフィボナッチのようになります。 =3 X_i + X_i +1=すべてのi+2に対してX_i+2 <=n ここで、シーケンスを形成する厳密に増加する配列Aを想定し、Aの最長のフィボナッチのようなサブシーケンスの長さを見つける必要があります。そのようなシーケンスがない場合は、0を返します。 したがって、入力がA =[1,2,3,4,5,6,7,8]のようである場合、次のシーケンス[1,2,3,5,8]があるため、出力は5になります。長さ5。 これを解決するには、次の手順に従います- s