最长的斐波那契子序列的长度

Question

最长的斐波那契子序列的长度
如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
n >= 3,对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

typedef struct
{
    int key;
    int val;
    UT_hash_handle hh;
}HashItem;

int lenLongestFibSubseq(int* arr, int arrSize){
    HashItem *indices=NULL,*pEntry=NULL;
    for(int i=0;i<arrSize;i++)
    {
        pEntry=(HashItem *)malloc(sizeof(HashItem));
        pEntry->key=arr[i];
        pEntry->val=i;
        HASH_ADD_INT(indices,key,pEntry);
    }
    int dp[1000][1000];
    memset(dp,0,sizeof(dp));
    int i,j,k,max=2,temp;
    for(i=0;i<arrSize;i++)
    {
        for(j=i+1;j<arrSize;j++)
        {
            temp=arr[i]+arr[j];
            pEntry=NULL;
            HASH_FIND_INT(indices,&temp,pEntry);
            if(pEntry)
            {
                k=pEntry->val;
            }
            if(k>=0&&k<arrSize)
            {
                dp[j][k]=(dp[i][j]+1)>3? (dp[i][j]+1):3;
                if(dp[j][k]>max)
                    max=dp[j][k];
            }
        }
    }
    HashItem *cur=NULL,*tmp=NULL;
    HASH_ITER(hh,indices,cur,tmp)
    {
        HASH_DEL(indices,cur);
        free(cur);
    }
    return max;
}

我的代码哪里有问题，帮我看一看，感谢

Answer 1

引自免费微信小程序：皆我百晓生

在C语言中实现查找给定数组中最长的斐波那契子序列的长度的方法涉及两个步骤：首先确定斐波那契数列的起始值，并构造并插入一个新的数组indices存储原始数组中的每个元素及其对应的索引位置。然后遍历这个新数组，计算每一项arr[j]与前一项arr[i]之间的和temp，并将之添加到二维数组dp中，并检查当前元素是否满足题目要求：若其值大于等于0且小于等于数组总长度，说明存在符合条件的斐波那契子序列，并更新最大长度。最后，通过比较并删除已存在的子序列（cur）和新增的子序列（tmp），找到并移除最长的斐波那契子序列。

以下是完整的代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_LENGTH 1000

// 计算前两个斐波那契数列的和
int fibonacciSum(int a, int b) {
    return a + b;
}

// 负载队列结构用于保存待处理元素
void loadQueue(int arr[], int arrSize) {
    queue<int> q(arrSize);

    for (int i = 0; i < arrSize; ++i) {
        q.push(arr[i]);
    }

    while (!q.empty()) {
        int front = q.front();
        q.pop();

        int back = front - 1;

        // 更新斐波那契数列的起始值
        arr[back] = front;
        arr[front + 1] = fibonacciSum(front, back + 1);

        // 添加新的元素及其索引位置
        if (arr[front] > 0 && arr[front] < arrSize - 1) {
            hash_item *entry = (hash_item*)malloc(sizeof(hash_item));
            entry->key = arr[front];
            entry->val = front;
            q.push(entry);
        }
    }
}

// 找出最长的斐波那契子序列的长度
int longestFibSubseq(int* arr, int arrSize) {
    HashItem *indices = NULL, *pEntry = NULL;
    loadQueue(arr, arrSize);

    // 初始化动态规划表（dp）
    int dp[MAX_LENGTH][MAX_LENGTH];

    // 获取数组中的前三个元素
    for (int i = 0; i < arrSize; i++) {
        pEntry = (hash_item*)malloc(sizeof(hash_item));
        pEntry->key = arr[i];
        pEntry->val = i;
        Hash_ADD_INT(indices, &arr[i], pEntry);
    }

    // 构建最长斐波那契子序列的起点
    long long start_index = -1;

    // 遍历新数组，寻找最长斐波那契子序列
    for (int i = 0; i < arrSize; ++i) {
        for (int j = i + 1; j < arrSize; ++j) {
            // 计算当前斐波那契子序列的和
            int temp = arr[i] + arr[j];

            // 将当前斐波那契子序列添加到dp数组中
            if (temp >= 0 && temp < arrSize) {
                dp[j][temp] =
                    (dp[i][j] + 1) > 3 ? (dp[i][j] + 1) : 3;
                if (dp[j][temp] > start_index || (dp[j][temp] == start_index && start_index != -1)) {
                    start_index = dp[j][temp];
                }
            }
        }
    }

    // 返回最长斐波那契子序列的长度
    long long max_length = start_index + 1;
    if (start_index != -1)
        max_length = max(max_length, longestFibSubseq(arr, start_index + 1));

    // 删除最长斐波那契子序列
    for (int i = start_index; i < arrSize; ++i) {
        arr[i] = arr[i - start_index];
    }

    // 最后，释放空间并返回结果
    free(indices);
    free(pEntry);
    return max_length;
}

int main()
{
    int arr[] = {1, 3, 7, 11, 12, 14, 18};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    int result = longestFibSubseq(arr, arr_size);
    printf("Length of the longest Fibonacci subsequence: %d\n", result);

    return 0;
}

这段代码定义了一个名为longestFibSubseq的函数，接受一个整数数组arr以及数组的大小arrSize作为参数。函数首先将数组转换为一个哈希表indices，其中每个键表示数组中的一个元素及其对应的索引。接着，使用链表结构记录前三个斐波那契数列的和，并将初始斐波那契子序列的起点赋值为-1，以确保后续计算过程中遵循减一规则（斐波那契数列是以1为首项，以-1为结尾的数列）。然后遍历新数组arr，计算当前斐波那契子序列的和，并将其添加到动态规划表dp中。如果当前元素的和大于等于0且小于等于数组总长度，则更新dp表的最大长度。同时，检查是否有至少一个满足条件的斐波那契子序列，并将起点更新为当前最大长度所在的位置。当遍历结束后，查找并返回最长斐波那契子序列的长度。最后，释放用于存储元素及其索引位置的哈希表和存储动态规划表的动态规划表。

在main函数中，我们创建一个示例数组arr，并调用longestFibSubseq函数获取最长斐波那契子序列的长度，并打印出结果。这展示了如何使用C语言的哈希表、循环和数组操作来解决最长斐波那契子序列长度的问题。