您现在的位置是：首页 >学无止境 >动态规划+哈希LeetCode-1027.最长等差数列网站首页学无止境

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：

输入：nums = [3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。

示例 2：

输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。

示例 3：

输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

提示：

• 2 <= nums.length <= 1000
• 0 <= nums[i] <= 500

遇到最值问题，我们可以往动态规划方法去想一想，此题可以用动态规划来进行解题，但这题还需要加上哈希表。动规五部曲（dp含义、递推公式、初始化、遍历顺序、打印数组） ，主要的就是把大问题拆解成小问题，小问题的值保存下来，从小问题的答案推导到最终答案，空间换时间。

题目及思路：大问题是求最长等差数列，那我们可以拆解成小问题，求出每个下标i位置的能构成的最长等差数列，使用双重循环遍历每个i和j<i的情况，检查是否能将nums[i]接在nums[j]后面形成更长的等差数列，从而更新dp[i]的值。但我们想到在这过程中会出现不同的公差然后构成等差数列，所以我们需要用到二维数组dp[i][d]表示以第i个元素结尾、公差为d的最长等差子序列的长度。
然后看到题目给的范围，出现公差可能会出现负数的情况，所以进行公差处理：我们将其转换为非负数索引（例如，加上500，使得公差范围为0到1000）。
每个元素自身可以视为长度为1的序列，因此将dp[i][d]数组初始化为1。

dp含义：二维数组dp[i][d]表示以第i个元素结尾、公差为d的最长等差子序列的长度。

初始化：每个元素自身可以视为长度为1的序列，因此将 dp 数组初始化为1。

递推公式：dp[i][d] = dp[i][d] > dp[j][d] + 1 ? dp[i][d] : dp[j][d] + 1;

遍历顺序：从前往后

打印数组：当遇到疑惑或者提交错误时，打印数组出来比较快速的看看哪一步有错。

以下是我在力扣c语言提交的代码，仅供参考：
 

int longestArithSeqLength(int* nums, int numsSize) {
    int dp[numsSize][1001];
    int max = 0;
    
    //初始化所有位置的公差为1
     for (int i = 0; i < numsSize; i++) {
        for (int d = 0; d < 1001; d++) {
            dp[i][d] = 1;
        }
    }

    for(int i = 1;i<numsSize;i++)
    {
        for(int j = 0;j<i;j++)
        {
            //公差d 并转换为0到1000的索引
            int d = nums[i] - nums[j] + 500 ;
           dp[i][d] = dp[i][d] > dp[j][d] + 1 ? dp[i][d] : dp[j][d] + 1;

            if(dp[i][d] > max)
            {
                max = dp[i][d];
            }
        }
    }
    return max;
}