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

Question

力扣093. 最长的斐波那契子序列的长度
如果序列 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] 的一个子序列）

int dp[1000][1000];  //dp[i][j]表示最后两个数下标为i、j的序列的长度
int search(int x,int * arr,int arrSize)  //返回数组arr中元素为x的下标，没有则返回-1
{
    int i;
    for(i=0;i<arrSize;i++)
    {
        if(x==arr[i])
            return i;
    }
    return -1;
}
int lenLongestFibSubseq(int* arr, int arrSize){
    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++)
        {
            dp[i][j]=dp[i][j]>2? dp[i][j]:2;  //第一次长度为2，到后面这两个结尾可能之前出现过
            temp=arr[i]+arr[j];
            k=search(temp,arr,arrSize);
            if(k!=-1&&k>j)
            {
                dp[j][k]=dp[i][j]+1;
                if(max<dp[i][j])
                    max=dp[i][j];
            }
        }
    }
    return max;
}

我的代码哪里有问题捏？

Answer 1

噜啦噜啦噜呼呼呼 晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

你的代码存在以下问题：

1. 初始化dp数组时，使用memset函数是不正确的，因为dp数组不是一个简单的二维数组，而是一个动态规划的数组，需要使用循环进行初始化。
2. 在循环中，你将dp[i][j]的值设为dp[i][j]>2 ? dp[i][j] : 2，这是错误的。因为从arr[i]和arr[j]，到后面的arr[k]（k>j）可能形成的斐波那契式的最大长度不一定是2，应该是dp[i][j]+1。
3. 在更新dp[j][k]的值时，你没有根据当前的dp[i][j]是否大于等于2进行判断和更新max的值，这也是错误的。

修改后的代码如下：

#include <stdio.h>
#include <string.h>

int search(int x, int *arr, int arrSize) {
    int i;
    for (i = 0; i < arrSize; i++) {
        if (x == arr[i])
            return i;
    }
    return -1;
}

int lenLongestFibSubseq(int *arr, int arrSize) {
    int dp[1000][1000];  // dp[i][j]表示最后两个数下标为i、j的序列的长度
    memset(dp, 0, sizeof(dp));

    int i, j, k, max = 0;
    for (i = 0; i < arrSize; i++) {
        for (j = i + 1; j < arrSize; j++) {
            k = search(arr[i] + arr[j], arr, arrSize);
            if (k != -1 && k > j) {
                dp[j][k] = dp[i][j] + 1;
                if (dp[j][k] > max)
                    max = dp[j][k];
            }
        }
    }

    return max >= 2 ? max + 2 : 0;
}

这样修改后的代码应该能够正确计算最长的斐波那契子序列的长度。