线性动态规划：等差数列划分 II - 子序列 题目描述 给定一个整数数组 nums，返回数组中所有为等差数列的子序列个数。如果一个序列中至少有三个元素，并且任意两个相邻元素之差相同，则称该序列为等差数列。子序列是从数组中删除一些（也可能不删除）元素后得到的序列，不需要连续。 示例： 输入：nums = [ 2,4,6,8,10 ] 输出：7 解释：所有等差数列子序列为： [ 2,4,6 ] [ 4,6,8 ] [ 6,8,10 ] [ 2,4,6,8 ] [ 4,6,8,10 ] [ 2,4,6,8,10 ] [ 2,6,10 ] 解题过程 第一步：理解问题本质 这个问题要求统计所有长度≥3的等差数列子序列个数。与连续子数组不同，子序列可以不连续，这增加了难度。我们需要找到所有满足等差条件的子序列组合。 第二步：分析关键难点 子序列不要求连续，需要考虑所有可能的元素组合 等差条件：任意相邻元素差值相同 需要统计所有长度≥3的序列 第三步：动态规划状态设计 我们使用dp[ i][ d ]表示以第i个元素结尾，公差为d的弱等差序列个数（长度≥2）。这里的"弱"是指包含长度为2的序列，因为长度为2的序列是构建更长序列的基础。 由于公差d可能是任意整数，我们使用哈希表来存储： dp[ i]：一个哈希表，键为公差d，值为以nums[ i ]结尾、公差为d的弱等差序列个数 第四步：状态转移方程 对于每个位置i，我们检查所有j < i： 计算公差d = nums[ i] - nums[ j ] 如果dp[ j]中存在公差d的序列，那么这些序列都可以延长到nums[ i ] 同时，nums[ j]和nums[ i ]本身也构成一个长度为2的新序列 状态转移方程： dp[ i][ d] += dp[ j][ d ] + 1 其中dp[ j][ d]表示以nums[ j]结尾的公差为d的序列个数，+1表示新增长的度为2的序列[ nums[ j], nums[ i] ]。 第五步：统计最终结果 在填充dp数组时，我们同时统计结果： 当dp[ j][ d] > 0时，说明存在以nums[ j]结尾的长度≥2的序列，此时将nums[ i]加入后，序列长度≥3，因此将dp[ j][ d ]加入最终结果。 第六步：具体实现步骤 初始化dp为长度为n的数组，每个元素是一个空哈希表 初始化结果ans = 0 遍历i从0到n-1： 遍历j从0到i-1： 计算d = nums[ i] - nums[ j ] 获取dp[ j ]中公差d对应的序列个数cnt（如果不存在则为0） 将cnt加入ans（这些序列延长后长度≥3） 更新dp[ i][ d ] += cnt + 1 返回ans 第七步：示例验证 以nums = [ 2,4,6,8,10 ]为例： i=0: dp[ 0 ] = {} i=1: 检查j=0, d=2, dp[ 1][ 2 ] = 0+1=1 i=2: 检查j=0, d=4 → dp[ 2][ 4 ] = 0+1=1 检查j=1, d=2 → cnt=dp[ 1][ 2]=1, ans+=1, dp[ 2][ 2 ] = 1+1=2 i=3: 检查j=0, d=6 → dp[ 3][ 6 ] = 1 检查j=1, d=4 → cnt=dp[ 1][ 4 ]=0 检查j=2, d=2 → cnt=dp[ 2][ 2]=2, ans+=2, dp[ 3][ 2 ] = 2+1=3 ... 最终统计所有长度≥3的序列，得到结果7。 第八步：复杂度分析 时间复杂度：O(n²)，需要两重循环 空间复杂度：O(n²)，最坏情况下每个位置可能存储O(n)个不同的公差 这种方法通过动态规划巧妙地统计了所有可能的等差数列子序列，确保了不重不漏的计数。