[数据结构与算法]Leetcode-1027最长等差数列

和最长上升子序列类似，这里多加了公差的性质，第一种想法是开一个结构体dp一维数组，dp[i].val表示以i位置结尾的最长长度，dp[i].cha表示以i位置结尾的子序列公差，你会发现无法进行状态转移，假设i<j<k，dp[k]被dp[j]更新了，并且更新后长度最大，但这不代表i这个位置就一定不是最长等差序列之一，因为可能dp[i].val和dp[j].val只相差1甚至相同，但两者公差不一样，如果后面再来几个公差和dp[i].cha一样的，而你又没有把k位置给添加到序列中，这个状态没有被考虑，导致错误。
因此需要dp[i][j]表示第i个位置添加到末尾并且公差是j的最长长度。
之后再仿照最长上升子序列进行更新即可。

int dp[1100][1100];
class Solution {
public:    
    int longestArithSeqLength(vector<int>& nums) {
        memset(dp,0,sizeof dp);
        int len=nums.size();
        int res=0;
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                dp[i][nums[i]-nums[j]+500]=max(dp[j][nums[i]-nums[j]+500]+1,dp[i][nums[i]-nums[j]+500]);
                res=max(res,dp[i][nums[i]-nums[j]+500]);
            }
        }
        return res+1;
    }
};