type
status
date
slug
summary
tags
category
icon
password
LeetCode上的一道中等难度题，在专项训练二分查找时录入，但其实是动态规划题目。
📝 题目
给你一个整数数组
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表，考虑对序列的长度进行动态规划，我们设定
dp[i][j] = num ，i为nums中第i位的数，j为公差，而num则为第i位数以j为公差的最长长度，由于公差有可能为负，因此我们开设的空间的大小范围应当为[-500, 500]。📎 参考文章
- LeetCode Wiki题解
有什么问题请留言，动态规划的思想会在之后的文章中讲解
- Author:灵檠
- URL:https://blog.ly-qing.lol/article/439d6c02-1c5b-4576-a347-43d28ebce51f
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!