# Dynamic Programming, Java Solution with detailed explanation!

• Given an array `a1, a2, ..., ai, ..., an`
`T(i,d)` is the number of arithmetic subsequence with difference d that ends at `ai`

Thus, we have `T(i,d) = sum(T(j,d) + 1)` for all the`j < i`and `ai - aj = d`
`T(0, d) == 0`

Consider the range of d could be from`[Integer.MIN_VALUE, INTEGER.MAX_VALUE]`, it would be too space-consuming to initialize such 2-d array. However, we can combine the 1-d array with the hashmap to create a new dynamic 2-d array.

In general, for this definition, it assumes that the length of subseqeunce can be`>= 2`. However, according to the question, we only count subsequence of which the length is`>= 3`. For example, given array `[1, 2, 3]` , `1, 2` is also considered to be a legal arithmetic sequence, but what we need to is just `1, 2, 3`.

And it is hard to adjust the definition above, because we need to know the length of subsequence, but the above definition does not provide this information. So we can only filter the 2 length subsequence in the code. Moreover, in the code below, we can only count the sequence of which the length is at least 4, 5, or more based on the requirement of problem.

Special thanks to fun4LeetCode.

``````public class Solution {
public int numberOfArithmeticSlices(int[] A) {
if (A == null || A.length == 0) return 0;

Map<Integer, Integer>[] map = new Map[A.length];         // dynamic 2-d array
// <d, #>
int res = 0;

for (int i = 0; i < A.length; i++) {
map[i] = new HashMap<>();
for (int j = 0; j < i; j++) {
long diff = (long)A[i] - A[j];
if (diff > Integer.MAX_VALUE || diff < Integer.MIN_VALUE) continue;
int d = (int) diff;
int T_jd = map[j].getOrDefault(d, 0);
int increase = T_jd + 1;            // the amount of increase for each time

/* This statement is used to adjust the acceptable subsequnce based on the requirement of problem
If the minimum length of subsequence should be 3, then res += increase > 1? (increase-1) : 0; Or simply res += increase-1;
If the minimum length of subsequence should be 4, then res += increase > 2? (increase-2) : 0;
If the minimum length of subsequence should be 5, then res += increase > 3? (increase-3) : 0;
...
...
...
*/
res += increase > 1? (increase-1) : 0;  //filter
map[i].put(d, map[i].getOrDefault(d, 0) + increase);
}
}
return res;

}
}
``````

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