看似动态规划，实则不需要——等差数列划分

看似动态规划，实则不需要——等差数列划分

原题：等差数列划分
老规矩，先看看能否用递归解。

转换

假设现在的数列为[1,2,3,4,5,6]，要怎么才能找出其子数列中所有的等差数列而无遗漏呢？
很容易想到，我们可以找出其所有子数列中以某数开头或者以某数结尾的等差数列。
这里就拿找出所有以某数结尾的等差数列举例。
假设要找出[1,2,3,4,5,6]的子数列中所有的等差数列，只需把问题转换为分别找出这个数列的所有子数列中以i（i in [1,2,3,4,5,6]）结尾并将其求和即可。

是否能分解为子问题

考虑一般的情况，以数列nums中的第i（i>2）个元素结尾的等差数列，那么根据是否满足nums[i] - nums[i - 1] = nums[i - 1] - nums[i - 2]会有以下两种情况：

1.满足，则为所有以第i-1个元素结尾的等差数列的数量加一。
2.不满足，则为零。

为什么是加一？
这多的一个哪里来的？首先很容易想到，若满足上述等式，则以第i-1个元素结尾的所有等差数列再加上第i个元素则可以成为等差数列。
那么多的那一个是什么呢？

nums[i - 2], nums[i - 1], nums[i]

即第i个，第i-1个，和第i-2个元素构成的数列。
至于为什么，因为在nums[i]没有加入前，这个数列只有两个元素，而前者加入后，这个数列就满足等差数列元素个数大于等于3这一要求了。
我们很容易看出，这个问题可以分解为更小的子问题。

是否满足最优子结构

显然，若为上述第一种情况，以第i个元素结尾的等差数列个数是由其子问题的个数加一得出的，满足最优子结构。

是否存在递归基

考虑最基本的情况：

1.若元素个数小于3，则为0；
2.若元素个数等于3，则判断是否满足等式，然后分解为子问题。

故递归基为有1，2个元素的情况。

递归求解

由于题目经过转换，故需要借助辅助函数求解：

int numberOfArithmeticSlices(vector& nums) {
	int sum = 0;
	for (int i = 2; i < nums.size(); ++i) {	//对所有以第i(i>2)个元素结尾的等差数列个数求和
		sum += helper(nums, i);
	}
	return sum;
}

int helper(vector& nums, int n) {	//以nums[n]结尾的等差数列的个数
	return n + 1 < 3 ? 0 : nums[n] - nums[n - 1] == nums[n - 1] - nums[n - 2] ? helper(nums, n - 1) + 1 : 0;
}

动态规划？

我们之前说过，之所以使用动态规划是因为存在着大量重复子问题，而这道题，事实上并不存在。
因为他的递推关系是这样的：

并没有重复子问题，故使用动态规划并不能得到优化，或者说，并不需要动态规划。
但是仍可用动态规划求解，这里就只放出空间优化后的版本。

int numberOfArithmeticSlices(vector& nums) {
    int n = nums.size();
    if (n < 3) return 0;
    int pre = 0, cur, sum = 0;
    for (int i = 2; i < n; ++i) {
        if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
            cur = pre + 1;
            pre = cur;
            sum += cur;
        }
        else pre = 0;
    }
    return sum;
}