# 200ms C++ DP solution

• ``````class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int count = 0, n = (int)A.size();
if (n == 0) return 0;
unordered_map<long, set<int>> indices;
for (int i = 0; i < n; ++i)
indices[(long)A[i]].insert(i);
vector<vector<int>> counts(n, vector<int>(n, 0));
for (int j = 1; j < n - 1; ++j) {
for (int k = j + 1; k < n; ++k) {
long prev = (long)A[j] + A[j] - A[k];
if (prev < INT_MIN || prev > INT_MAX || !indices.count(prev))
continue;
for (int i : indices[prev]) {
if (i >= j) break;
counts[j][k] += counts[i][j] + 1;
}
count += counts[j][k];
}
}
return count;
}
};
``````

`counts[j][k]` is the count of sequences (with lengths greater than 2) ending with indices `j` and `k`.
`counts[j][k] = sum{counts[i][j] + 1 | A[i] - A[j] == A[j] - A[k] and i < j}`

Obviously, this solution is not as good as those O(n^2) DP solutions. Any idea why it takes much less time to AC?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.