413. Arithmetic Slices

算法
动态规划 
A sequence of number is called arithmetic if it consists of at least three elements and 
if the difference between any two consecutive elements is the same.

Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

题目的意思是求一个给定数组的等差数列子集的个数。是一个动态规划的题，一开始用一个两层的循环分割数组长度，再用一个循环判断是否是等差数列，这样自然就是超时了。
用动态规划的思想，用一个数组来存储含有i的等差子集个数，如果一个等差数列，新加入的那个元素也满足和前一个数等差，那么可以得到递归公式：

最后求出数组count的和就是含有所有数字的等差子集的个数，即数组所有等差数列子集的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var numberOfArithmeticSlices = function(nums) {
        let count  = new Array(nums.length+1)
        count.fill(0)
        for(let i=2; i<nums.length; i++){
            if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){
                count[i] = count[i-1] + 1
            }
        }
 
        let sum = 0
        for(let i=0; i<count.length; i++){
            sum += count[i]
        }
 
        return sum
    };