**Solution**

**Arithmetic Slices II - Subsequence** https://leetcode.com/problems/arithmetic-slices-ii-subsequence/

**Dynamic Programming Solution**

- sub_problem[i,d] = Number of arthimetic sequences of length 2 or more which end at index i and have difference as d. Note we said length 2 or more and not 3.
- Say we have an array called cache where every element of cache is a dictionary. The key for dictionary is difference d and value is number of sequences which end at i with difference d.
- sub_problem[i,d] = sub_problem[j,d] + 1 iff A[i]-A[j] == d. The 1 in this equation represents the new subsequence of size 2 comprising of A[j], A[i]. Imagine array [2,2,3,4]. Say we are at index 2. Now we want to find the distribution of all sequences which end at index 2. Now for index 1 and 0, we notice a size 2 sequence of (2,3) and (2,3). These two would be added in the count of all subsequences ending at i.
- We maintain a count of all size 2 subsequences and call it subs_len_2. Once we are done processing an index, we add all subsequences which end at index i to result. Finally we remove the count of size 2 subsequences from result and return the result.

```
from collections import defaultdict
class Solution(object):
def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
cache = [defaultdict(int) for _ in range(len(A))]
result, subs_len_2 = 0, 0
for i in range(1, len(A)):
for j in range (i-1,-1,-1):
curr_diff = A[i]-A[j]
cache[i][curr_diff], subs_len_2 = cache[i][curr_diff]+1, subs_len_2+1
if curr_diff in cache[j]:
cache[i][curr_diff] += cache[j][curr_diff]
result += sum(cache[i].values())
return result - subs_len_2
```

**Succinct Code**

- The above code can be made a bit more clever so that we do not need to maintain a count of size 2 subsequences.

```
class Solution1(object):
def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
cache = [{} for _ in range(len(A))]
result = 0
for i in range(1, len(A)):
for j in range (i-1,-1,-1):
curr_diff = A[i]-A[j]
cache[i].setdefault(curr_diff, 0)
cache[i][curr_diff] += 1
if curr_diff in cache[j]:
cache[i][curr_diff] += cache[j][curr_diff]
result += cache[j][curr_diff]
return result
```