简单的动归，若i-2, i-1, i等差，则以第i个数结尾的等差数列总数=以i-1个数结尾的等差数列总数+1。需要多加考虑，自己的想法是求出每一段的最长等差数列，然后求和即可，效率不高。
自己的代码
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int i = 1, output = 0, length = 0;
while (i < A.size()){
if (i != A.size() - 1 && A[i] - A[i-1] == A[i+1] - A[i]){
++length;
}else{
while (length != 0){
output += length;
--length;
}
}
++i;
}
return output;
}
};
DP解法
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int n = A.size();
if (n < 3) return 0;
vector<int> dp(n, 0); // dp[i] means the number of arithmetic slices ending with A[i]
if (A[2]-A[1] == A[1]-A[0]) dp[2] = 1; // if the first three numbers are arithmetic or not
int result = dp[2];
for (int i = 3; i < n; ++i) {
// if A[i-2], A[i-1], A[i] are arithmetic, then the number of arithmetic slices ending with A[i] (dp[i])
// equals to:
// the number of arithmetic slices ending with A[i-1] (dp[i-1], all these arithmetic slices appending A[i] are also arithmetic)
// +
// A[i-2], A[i-1], A[i] (a brand new arithmetic slice)
// it is how dp[i] = dp[i-1] + 1 comes
if (A[i]-A[i-1] == A[i-1]-A[i-2])
dp[i] = dp[i-1] + 1;
result += dp[i]; // accumulate all valid slices
}
return result;
}
};
