413. 等差数列划分

https://leetcode-cn.com/problems/arithmetic-slices/

解法一：暴力

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

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动图解释。状态方程：dp[i] = dp[i-1]+1，dp[i]表示在i位置结尾的序列所含有的等差数列个数。

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

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

再看序列：

A[a...i]

A[a...i+1]

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

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