leetcode413 等差数列划分

　　关键在于如何定义问题进行分治：

　　1. 问题的定义必须可以覆盖解空间。

　　2. 问题的解可由子问题的解表示，也就是状态转移关系。

　　划分问题，无非就是：按区间划分，找出区间与区间的关系，最后的问题覆盖整个问题入参区间；按点划分，找出点与点的关系，最后合并所有点的结果覆盖整个问题入参区间。

　　对于解题来说，无论是暴力遍历还是分而治之，该有的计算量一点都不会少。因此想象一下暴力求解时是不断的扩大入参区间求区间结果还是一个点一个点的求结果最后累加可以为如何定义分治问题提供参考。

　　但在定义时还需考量问题的定义是否使得解决问题的过程中存在重复计算，因为分治提高效率很重要的一个原因便是通过缓存避免重复计算。

　　如果问题实在难以定义，思考暴力求解时是否使用到了回溯。如果问题的定义使得函数存在副作用，需要想办法消除这些副作用。消除副作用需要在一些逻辑上做反转，比如使用变为不使用、无序的变为有序的、以某个元素开头变为以某个元素结尾等等。

 /**
     * @Author Niuxy
     * @Date 2020/6/17 8:01 下午
     * @Description G(n) 为前 n 个元素中，以第 n 个元素结尾的等差数列的个数
     * if A[n]-A[n-1]=A[n-1]-A[n-2]
         * if G(n-1)!=0
            * G(n)=G(n-1)*2+1
        * else if A[n-1]-A[n-2]==A[n-2]-A[n-3]
             * G(n)=1
         * else
            * G(n)=0
     */

    public final int numberOfArithmeticSlices(int[] A) {
        if (A.length < 3) {
            return 0;
        }
        int[] dp = new int[A.length];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = (A[2] - A[1]) == (A[1] - A[0]) ? 1 : 0;
        int re = dp[2];
        for (int i = 3; i < dp.length; i++) {
            if ((A[i] - A[i - 1]) == (A[i - 1] - A[i - 2])) {
                if (dp[i - 1] != 0) {
                    dp[i] = dp[i - 1] + 1;
                } else if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                    dp[i] = 1;
                }
            } else {
                dp[i] = 0;
            }
            re += dp[i];
        }
        return re;
    }

　　dp[i] 只与 dp[i-1] 有关，因此不需要缓存 dp[i-1] 之前的结果。优化一些空间复杂度：

public final int numberOfArithmeticSlices2(int[] A) {
        if (A.length < 3) {
            return 0;
        }
        int pre = (A[2] - A[1]) == (A[1] - A[0]) ? 1 : 0;
        int re = pre;
        for (int i = 3; i <A.length; i++) {
            if ((A[i] - A[i - 1]) == (A[i - 1] - A[i - 2])) {
                if (pre != 0) {
                    pre += 1;
                } else if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                    pre = 1;
                }
            } else {
                pre = 0;
            }
            re += pre;
        }
        return re;
    }