BiruLyu
7/7/2017 - 5:28 PM

## 3ms C++ Standard DP Solution with Very Detailed Explanation.cpp

``````public int numberOfArithmeticSlices(int[] A) {
int curr = 0, sum = 0;
for (int i=2; i<A.length; i++)
if (A[i]-A[i-1] == A[i-1]-A[i-2]) {
curr += 1;
sum += curr;
} else {
curr = 0;
}
return sum;
}``````
``````def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
opt, i = [0,0], 1
for j in xrange(2,len(A)):
if A[j]-A[j-1] == A[j-1]-A[j-2]:
opt.append(opt[j-1]+i)
i += 1
else:
opt.append(opt[j-1])
i = 1
return opt[-1]``````
``````public class Solution {
public int numberOfArithmeticSlices(int[] A) {
if (A == null || A.length < 3) return 0;
int len = A.length;
int sum = 0;
int cur = 1;
for (int i = 2; i < len; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
sum += cur;
cur++;
} else {
cur = 1;
}
}
return sum;
}
}``````
``````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;
}
};``````