# 413. 等差数列划分

[https://leetcode-cn.com/problems/arithmetic-slices/](https://leetcode-cn.com/problems/arithmetic-slices/)

## 解法一：暴力

i作为序列头,从0开始到N-3遍历数组,首先找一个最短的等差序列(长度为3),找到后算出间距dist,再以j为序列尾,从i+3开始到N向后扩张,看等差序列是否还存在后续.只要找到一个间距不等于dist,表明在这里断开,退出内层j循环,序列头后移一位.如此往复

```cpp
int numberOfArithmeticSlices(vector<int>& A) {
    int N = A.size();
    int count = 0;
    if (N < 3) return 0; //特殊情况处理
    for (int i = 0; i < N-2; i++) { //遍历0到N-3的位置
        if (A[i+1] - A[i] != A[i+2] - A[i+1]) continue;  //A[i,i+1,i+2]不满足等差数列,直接跳过本次循环
        int dist = A[i+1] - A[i];  //等差间距distance
        count++;  //找到一个等差
        for (int j = i+3; j < N; j++) {  //j从i+2之后找,看等差序列是否还存在后续
            if (A[j] - A[j-1] != dist) break;  //只要发现一个不等的,立即退出循环
            count++;
        }
    }
    return count;
}
```

## 解法二：dp

本题与5.最长回文子串 还是有些许不同，主要是等差数列不一定要看首尾，因此用i，j表示开头结尾，用二维dp矩阵表示状态就不太适用。例如1,2,3,4就可以来自1,2,3或2,3,4，不好确定来自哪一个，有可能会重复计数。

见[sulution](https://leetcode.com/problems/arithmetic-slices/solution/)动图解释。状态方程：`dp[i] = dp[i-1]+1`，dp\[i]表示在i位置结尾的序列所含有的等差数列个数。&#x20;

若序列：`A[a...i]` 中，以i结尾的等差个数为`dp[i]`，若满足`A[i+1]-A[i] == A[i]-A[i-1]`&#x20;

则序列： `A[a...i+1]` 中，以i+1结尾的等差个数为`dp[i]+1`，多出的一个以i+1结尾的序列为`A[i-1,i,i+1]`，长度为3

再看序列：

`A[a...i]`&#x20;

`A[a...i+1]`&#x20;

记a到i的等差数列总个数为`sum` ，则若`dp[i]!=0`，a到i+1的总个数为`sum+dp[i]`。 解释：序列多了A\[i+1]，此前的所有情况都增加1，即等差数列总个数增加`dp[i]*1`

```python
class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        n = len(A)
        if n < 3:
            return 0
        dp = [0] * n
        sum = 0
        for i in range(2, n):
            if A[i]-A[i-1] == A[i-1]-A[i-2]:
                dp[i] = dp[i-1]+1    #状态方程
                sum += dp[i]    #累加
        return sum
```
