1.题目基本信息

1.1.题目描述

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。

• 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。

• 再例如，[1, 1, 2, 5, 7] 不是等差序列。

数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。

• 例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

题目数据保证答案是一个 32-bit 整数。

1.2.题目地址

https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/description/

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

第一步，状态定义。dp[i][d]为以nums[i]结尾，方差为d的弱等差序列的个数（弱等差序列为长度至少为2的等差序列）

第二步，状态初始化。默认设置dp[][]=0

第三步，状态转移。遍历nums的索引有序对(i,j)(其中0<=i<j<len(nums))，dp[j][nums[j]-nums[i]]+=dp[i][nums[j]-nums[i]]+1（其中加的1指的是[nums[i],nums[j]]这一只有俩元素的弱等差序列）

第四步，在状态转移的过程中，dp[i][nums[j]]对应的数列在增加元素nums[j]后，元素个数一定大于等于3，所以可以构建成合法等差序列，进行累加即为题解

3.解题代码

python代码

from collections import defaultdict

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        # 思路：动态规划
        # 第一步，状态定义。dp[i][d]为以nums[i]结尾，方差为d的弱等差序列的个数（弱等差序列为长度至少为2的等差序列）
        n = len(nums)
        dp = [defaultdict(int) for _ in range(n)]
        # 第二步，状态初始化。默认设置dp[*][*]=0
        # 第三步，状态转移。遍历nums的索引有序对(i,j)(其中0<=i<j<len(nums))，dp[j][nums[j]-nums[i]]+=dp[i][nums[j]-nums[i]]+1（其中加的1指的是[nums[i],nums[j]]这一只有俩元素的弱等差序列）
        result = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                d = nums[j] - nums[i]
                result += dp[i][d]
                dp[j][d] += dp[i][d] + 1
        # 第四步，在状态转移的过程中，dp[i][nums[j]]对应的数列在增加元素nums[j]后，元素个数一定大于等于3，所以可以构建成合法等差序列，进行累加即为题解
        return result

4.执行结果