413. 等差数列划分
这个题目就相当于动态规划的一个变式了，只有深入理解了动态规划，才能容易想到。
题目描述
数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
如果满足以下条件，则称子数组(P, Q)为等差数组：
元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。
函数要返回数组 A 中所有为等差数组的子数组个数。
示例:A = [1, 2, 3, 4]返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
题解
这道题该怎么使用动态规划呢？
之前遇到的动态规划问题，都是使用dp直接用于结果的输出，但这道题目稍微有点特殊。
我们可以注意到一个等差数组的个数可以由上一个等差数组的状态来决定。
比如例子：[1,2,3,4]
- 已知【1,2,3】可以构成一个等差数列 dp = 1
- 当加入新的元素7时，仍然满足等差数列 即【1,2,3,4】
- 此时dp = dp[i-1]+1 =2 加一对应的是【2,3,4】。
- 总结规律，每当新的元素仍然满足等差数列时，对应元素i的等差数列个数为之前的等差数列数+1
- 总的等差数列的个数 为 所有元素对应的等差数列求和
- sum =Sum(dp) = 1+2 =3
对代码进行优化 ：
对于当前时刻i的等差数列的个数 只和前一时刻的等差数列的个数有关，因此可以仅使用常数空间就行求解。
代码
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int len = nums.length;if(len < 3){
return 0;}int[] dp = new int[len+1];for(int i=0;i<len+1;i++){
dp[i]= 0;}for(int i=2;i<len;i++){
if(nums[i]-nums[i-1] == nums[i-1] - nums[i-2]){
dp[i]= dp[i-1] +1;}}int ret = 0;for(int i=0;i<len+1;i++){
ret += dp[i];}return ret;}
}
代码优化：
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int len = nums.length;if(len < 3){
return 0;}int dp = 0;int sum = 0;for(int i=2;i<len;i++){
if(nums[i] - nums[i-1] == nums[i-1] -nums[i-2]){
dp = dp+1;sum += dp;}else{
dp=0;}}return sum; }
}