【动态规划】最长斐波那契数列和最长等差数列

今天总结一下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& arr) {
        int n=arr.size();
        unordered_map Index;
        for(int i=0;i longest;
        for(int i=0;i=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& nums) {
        int n=nums.size();

        vector> dp(n,vector(1001,0));
        int res=0;
        for(int i=0;i