今天总结一下Leetcode上的两道看可以用同一解法实则不可生搬硬套的两道相似题。

1、873. 最长的斐波那契子序列的长度 - 力扣（LeetCode） (leetcode-cn.com)

本题的难点在于状态定义：与一般的dp题不同，这里我们选择将dp数组定义为：dp[i][j]表示以arr[i],arr[j]结尾的斐波那契数列的最大长度。因为想要确定一个斐波那契数列需要三个值arr[i],arr[j],arr[k],如果直接定义首先会出现一个三重循环，并且许多细节难以言表。。。将状态转移数组定义成上述表示可以根据性质:arr[k]+arr[i]=arr[j]来确定k的值，减小循环数。为了获取下标需要一个hash表来将各个元素的下标提取出来（由于数组严格递增，所以我们不用担心重复问题）。k由Index[arr[i]-arr[j]]唯一确定。

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n=arr.size();
        unordered_map<int,int> Index;
        for(int i=0;i<n;i++){
            Index[arr[i]]=i;
        }
        int res=0;
        unordered_map<int,int> longest;
        for(int i=0;i<n;i++){
            for(int k=0;k<i;k++){
                if(Index.count(arr[i]-arr[k])&&arr[i]-arr[k]<arr[k]){
                    int j=Index[arr[i]-arr[k]];
                    longest[k*n+i]=longest[j*n+k]+1;
                    res=max(res,longest[k*n+i]+2);
                }
            }
        }
        return res>=3?res:0;
    }
};

时间复杂度：O(n²)

2、1027. 最长等差数列 - 力扣（LeetCode） (leetcode-cn.com)

这道题与上一道题十分相似，像我这样的新手很容易惯性思维直接套用上题的解法。但其实在这里是有问题的。因为题目中给定的数组nums并没有说明是严格递增的，这意味着数组中可能会出现重复元素，从而在确定第三维的下标时产生重复。因此在这里我们将状态定义为：dp[i][j]表示以nums[i]结尾的公差为j的等差数列的最大长度。根据题目所给的数据范围：0<=nums[i]<=500我们可以确定公差的范围-500<=d<=500，因此我们将公差加上500使之恒正，便于我们定义dp数组。根据nums[i]-nums[j]+500来唯一确定公差。其他的便与LIS算法相似。

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n=nums.size();

        vector<vector<int>> dp(n,vector<int>(1001,0));
        int res=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                int d=nums[i]-nums[j]+500;
                dp[i][d]=max(dp[i][d],dp[j][d]+1);
                res=max(res,dp[i][d]);
            }
        }
        return res+1;
    }
};