LeetCode-413-等差数列划分

image.png

image.png

解题思路：

1. dp[i]=dp[i-1]+1，由dp表示当前点i所包含的等差数列数，其状态转移方式：比前一个状态多了1，如数列1[1, 2, 3]的dp[2]值为1，而数列2在数列1的基础上加了4，[1, 2, 3, 4]的dp值因为比dp[3]=2，而数列2包含的所有子数组个数即dp值的和=3；
2. 假设输入数组A为长度为n的等差数列，则返回 (n-1)*(n-2)/2个子数组，因此找出A的子最大等差数列，然后分别求其子数组个数，再求和。

Python3代码

  class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        sum1 = 0
        dp = [0 for _ in range(len(A))]
        for i in range(2,len(A)):
            if A[i] - A[i-1] == A[i-1]-A[i-2]:
                sum1+=1
                dp[i]=sum1
            else:
                sum1=0
                dp[i]=0
        return sum(dp)

Python3代码

class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        r = 0
        i = 0
        while i < len(A)-2:
            len1 = 2
            while i+2<len(A) and A[i + 2] - A[i + 1] == A[i + 1] - A[i]:
                len1+=1
                i+=1
            i+=1
            r += int((len1-1)*(len1-2)/2)
        return r