Given an array A of N positive integers. The task is to count the number of Arithmetic Progression subsequence in the array.
Note: Empty sequence or single element sequence is Arithmetic Progression. 
Example 1:
Input : 
N = 3
A[] = { 1, 2, 3 }
Output : 
8
Explanation:
Arithmetic Progression subsequence from the 
given array are: {}, { 1 }, { 2 }, { 3 }, { 1, 2 },
{ 2, 3 }, { 1, 3 }, { 1, 2, 3 }.
Example 2:
Input :
N = 3
A[] = { 10, 20, 30,} 
Output :
8
Explanation: 
Arithmetic Progression subsequence 
from the given array are: {}, { 10 }, 
{ 20 }, { 30 }, { 10, 20 }, { 20, 30 }, 
{ 10, 30 }, { 10, 20, 30 }.
Your Task:
You don't need to read input or print anything. Your task is to complete the function count() which takes an integer N and an array A as input parameters and returns the total count of AP sub-sequences in the array.
 
Expected Time Complexity: O(N * (Minimum value in A - Maximum Value in A)) 
Expected Space Complexity: O(N)
Constraints:
1<= N <=100
1<= A[i] <=100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def count(self,N,A):
        # code here

Solutions:
from collections import defaultdict

class Solution:

	def count(self, n, nums):
		n = len(nums)
		ans = 0
		dp = defaultdict(lambda : 0)
		for i in range(1, n):
			for j in range(i):
				delta = nums[i] - nums[j]
				ans += dp[j, delta]
				dp[i, delta] += dp[j, delta] + 1
		return ans + (n + 1) + n * (n - 1) // 2


class Solution:

	def count(self, N, arr):
		dp = [{} for i in range(0, N)]
		ans = N + 1
		for i in range(1, N):
			for j in range(0, i):
				diff = arr[i] - arr[j]
				val = 1 + dp[j].get(diff, 0)
				if diff in dp[i]:
					dp[i][diff] += val
				else:
					dp[i][diff] = val
				ans += val
		return ans


class Solution:

	def count(self, N, A):
		dp = []
		x = max(A) - min(A)
		y = min(A) - max(A)
		for i in range(N):
			d1 = {}
			dp.append(d1)
		c = N + 1
		for i in range(N):
			for j in range(i):
				if A[i] - A[j] not in dp[j]:
					dp[i][A[i] - A[j]] = 2
					c += 1
				else:
					c += dp[j][A[i] - A[j]]
					dp[i][A[i] - A[j]] = dp[j][A[i] - A[j]] + 1
		return c


class Solution:

	def count(self, n, a):
		mini = min(a)
		maxi = max(a)
		dp = [0 for i in range(n + 1)]
		r = n + 1
		for d in range(mini - maxi, maxi - mini + 1):
			sumi = [0 for i in range(100000)]
			for i in range(n):
				dp[i] = 1
				if a[i] - d >= 1:
					dp[i] += sumi[a[i] - d]
				r += dp[i] - 1
				sumi[a[i]] += dp[i]
		return r