413. Arithmetic Slices 算术切片
413. Arithmetic Slices 算术切片
第一种解法：二维DP
暴力考虑所有长度大于3的切片，这种方法较慢
更好的解法：一维DP
dp[i] 表示以 A[i] 结尾的切片的算术切片个数，在原有的算术切片的基础上再纳入一个新的数字，只会比以前一个结尾的多增加一个算术切片或者没有
int numberOfArithmeticSlices(vector<int>& A) {
int len=A.size();
vector<int> dp(A.size(), 0);
int res=0;
if (len>=3 && A[2]-A[1]==A[1]-A[0]) {
dp[2]=1;
res+=dp[2];
}
for(int i=3;i<len;++i) {
if (A[i]-A[i-1]==A[i-1]-A[i-2]) {
dp[i]=dp[i-1]+1;
}
res+=dp[i];
}
return res;
}#DP