413. 等差数列划分
1.题目
如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组个数。子数组是数组中的一个连续序列。
实例1：
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
实例2：
输入：nums = [1]
输出：0
提示：
1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000
2.思路
-
方法：动态规划
-
动态规划算法基础
-
基本思想： 将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解（这部分与分治法相似）。与
分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问
题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避
免大量的重复计算，节省时间。通常可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将
其结果填入表中。这就是动态规划的基本思路。 -
基本特点： 1)最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满组最优化原理。 2)无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。 3)有重叠问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
-
基本思路： 动态规划一般分为一维、二维，对应形式为 dp(i)、dp(i)(j)
(1)确定dp数组，以及下标含义
(2)确定递推公式
(3)dp数组如何初始化
(4)确定遍历顺序
(5)举例推导递推公式
-
-
动态规划方程：dp[i] = dp[i - 1] + 1
dp[i]表示以：nums(i）结尾的，且长度大于等于3的连续等差数列的个数
image.png
3.代码
def numberOfArithmeticSlices(nums: Array[Int]): Int = {
var len = nums.length
if(len<3) return 0
// dp[i]表示以：nums(i结尾的，且长度大于等于3的连续等差数列的个数
val dp = new Array[Int](len)
var res = 0
// 从下标2开始，才有可能构成长度至少大于等于3的等差数列
for(i<-2 until(len)){
if(nums(i)-nums(i-1)==nums(i-1)-nums(i-2)){
dp(i)=dp(i-1)+1
res = res + dp(i)
}
}
return res
}
4.复杂度分析
时间复杂度：O(N)，这里 N 是输入数组的长度；
空间复杂度：O(N)。由于 dp[i] 只参考了 dp[i - 1]，可以使用「滚动变量」优化空间复杂度。
