###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 413. Arithmetic Slices

## [題目連結:] https://leetcode.com/problems/arithmetic-slices/description/

## 題目:
An integer array is called arithmetic if it consists of **at least three elements** and if the difference between any two consecutive elements is the same.

* For example, ```[1,3,5,7,9]```, ```[7,7,7,7]```, and ```[3,-1,-5,-9]``` are arithmetic sequences.

Given an integer array ```nums```, return the number of arithmetic **subarrays** of ```nums```.

A **subarray** is a contiguous subsequence of the array.

**Example 1:**

Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

**Example 2:**

Input: nums = [1]
Output: 0

## 解題想法:
* 此題為求數組中，連續三個以上構成的等差序數列之總數

* 使用dp:
* 定義: **dp[i]為加入nums[i]之後可以多增加的組合數**
* 求等差序列數，3個為基底
* 每多再加一個數可多加n-2種組合
* ex: 對於目前(5,6)
* 若下個數為7，則可構成3個等差數 : 多加3-2=1種 -> (5 6 7):1種
* 若再下個數為8，可構成4個等差數 :多加4-2=2種 ->(5 6 7 8): 比上面多了 (678)、(5678)多加2種

ex:
nums=   1 2 3 4 6 8 10 12
dp[]    0 0 1 2 1 1  2  3  加入該數字可創造多少組
res     0 0 1 3 3 4  6  9  目前總共組數 res

## Python:

class Solution(object):
    def numberOfArithmeticSlices(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp=[0]*len(nums)
        res=0
        for i in range(2,len(nums)):
            if nums[i]-nums[i-1]==nums[i-1]-nums[i-2]:
                dp[i]=dp[i-1]+1
                res+=dp[i]
        return res
        
result = Solution()
ans = result.numberOfArithmeticSlices(nums=[1,2,3,4,6,8,10,12])
print(ans)

## C++:

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n=nums.size(), res=0;
        vector<int> dp(n,0);
        for (int i=2; i<n; i++){
            if ((nums[i]-nums[i-1])==(nums[i-1]-nums[i-2])){
                dp[i]=dp[i-1]+1;
                res+=dp[i];
            }
        }
        return res;
    }
};