Consider a game where a player can score 3 or 5 or 10 points in a move. Given a total score n, find number of distinct combinations to reach the given score.
Example:
Input
3
8
20
13
Output
1
4
2
Explanation
For 1st example when n = 8
{ 3, 5 } and {5, 3} are the 
two possible permutations but 
these represent the same 
cobmination. Hence output is 1.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function count( ) which takes N as input parameter and returns the answer to the problem.
Constraints:
1 ≤ T ≤ 100
1 ≤ n ≤ 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

def count(n):
    #your code here
    

Solutions:
def count(n):
	ans = [0] * (n + 1)
	ans[0] = 1
	for i in range(3, n + 1):
		ans[i] += ans[i - 3]
	for i in range(5, n + 1):
		ans[i] += ans[i - 5]
	for i in range(10, n + 1):
		ans[i] += ans[i - 10]
	return ans[n]


def count(n):
	a = [3, 5, 10]
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(len(a)):
		for j in range(a[i], n + 1):
			dp[j] += dp[j - a[i]]
	return dp[-1]


def solve(dp, a, i, n):
	if n < 0:
		return 0
	if dp[i][n] != -1:
		return dp[i][n]
	dp[i][n] = solve(dp, a, i, n - a[i]) + solve(dp, a, i - 1, n)
	return dp[i][n]

def count(n):
	a = [0, 3, 5, 10]
	(row, col) = (4, n + 1)
	dp = [[-1 for j in range(col)] for i in range(row)]
	for j in range(n + 1):
		dp[0][j] = 0
	for i in range(row):
		dp[i][0] = 1
	return solve(dp, a, row - 1, n)


def count(n):
	score = [3, 5, 10]
	res = [0] * (n + 1)
	res[0] = 1
	for i in range(3, n + 1):
		res[i] += res[i - 3]
	for i in range(5, n + 1):
		res[i] += res[i - 5]
	for i in range(10, n + 1):
		res[i] += res[i - 10]
	return res[n]


def count(n):
	stateMap = [0 for _ in range(n + 1)]
	stateMap[0] = 1
	for score in [3, 5, 10]:
		for state in range(1, n + 1):
			if state - score >= 0 and stateMap[state - score]:
				stateMap[state] += stateMap[state - score]
	return stateMap[-1]


def count(n):
	table = [0] * (n + 1)
	table[0] = 1
	points = [3, 5, 10]
	for i in range(3):
		for j in range(points[i], n + 1):
			table[j] += table[j - points[i]]
	return table[n]


def count(n):
	scores = [3, 5, 10]
	count = 0

	def recurs(i, sums):
		nonlocal count
		if i >= len(scores) or sums > n:
			return
		if sums == n:
			count += 1
			return
		sums += scores[i]
		recurs(i, sums)
		sums -= scores[i]
		recurs(i + 1, sums)
	recurs(0, 0)
	return count


def dynamic(n):
	nums = [3, 5, 10]
	dp = [0] * max(n + 1, 11)
	dp[0] = 1
	for num in nums:
		for i in range(num, n + 1):
			dp[i] += dp[i - num]
	return dp[n]

def count(n):
	return dynamic(n)


def count(n):
	dp = dict()

	def findcombi(remn, prev):
		if remn < 0:
			return 0
		if remn == 0:
			return 1
		if (remn, prev) in dp:
			return dp[remn, prev]
		val = 0
		if prev == 3:
			val += findcombi(remn - 3, 3)
			val += findcombi(remn - 5, 5)
			val += findcombi(remn - 10, 10)
		elif prev == 5:
			val += findcombi(remn - 5, 5)
			val += findcombi(remn - 10, 10)
		else:
			val += findcombi(remn - 10, 10)
		dp[remn, prev] = val
		return val
	return findcombi(n, 3)


def count(n):
	arr = [3, 5, 10]
	return noofways(n, 0, arr, {})

def noofways(n, currentIndex, arr, pathcheck):
	if n == 0:
		return 1
	if currentIndex == len(arr) or n < arr[currentIndex]:
		return 0
	currentKey = str(currentIndex) + '-' + str(n)
	if currentKey in pathcheck:
		return pathcheck[currentKey]
	leftNode = noofways(n - arr[currentIndex], currentIndex, arr, pathcheck)
	rightNode = noofways(n, currentIndex + 1, arr, pathcheck)
	pathcheck[currentKey] = leftNode + rightNode
	return pathcheck[currentKey]


def count(n):
	arr = [3, 5, 10]
	dp = [[-1 for i in range(n + 1)] for j in range(3)]

	def rec(idx, tar):
		if idx < 0:
			if tar == 0:
				return 1
			return 0
		if dp[idx][tar] != -1:
			return dp[idx][tar]
		pick = 0
		if tar >= arr[idx]:
			pick = rec(idx, tar - arr[idx])
		npick = rec(idx - 1, tar)
		dp[idx][tar] = pick + npick
		return dp[idx][tar]
	prev = [0 for i in range(n + 1)]
	curr = [0 for i in range(n + 1)]
	for i in range(n + 1):
		if i % arr[0] == 0:
			prev[i] = 1
	for i in range(1, 3):
		for j in range(n + 1):
			if j >= arr[i]:
				curr[j] = prev[j] + curr[j - arr[i]]
			else:
				curr[j] = prev[j]
		prev = curr[:]
	return prev[n]


def count(n):
	arr = [3, 5, 10]
	dp = [[-1 for i in range(n + 1)] for j in range(3)]

	def rec(idx, tar):
		if idx < 0:
			if tar == 0:
				return 1
			return 0
		if dp[idx][tar] != -1:
			return dp[idx][tar]
		pick = 0
		if tar >= arr[idx]:
			pick = rec(idx, tar - arr[idx])
		npick = rec(idx - 1, tar)
		dp[idx][tar] = pick + npick
		return dp[idx][tar]
	return rec(len(arr) - 1, n)


def count(n):
	arr = [3, 5, 10]

	def rec(idx, tar):
		if idx < 0:
			if tar == 0:
				return 1
			return 0
		pick = 0
		if tar >= arr[idx]:
			pick = rec(idx, tar - arr[idx])
		npick = rec(idx - 1, tar)
		return pick + npick
	return rec(len(arr) - 1, n)


def solve(n, val, v, dp):
	if n == 0:
		return 1
	if n < 0:
		return 0
	if v - 1 < 0:
		return 0
	if dp[n][v] != -1:
		return dp[n][v]
	if n >= val[v - 1]:
		dp[n][v] = solve(n, val, v - 1, dp) + solve(n - val[v - 1], val, v, dp)
	else:
		dp[n][v] = solve(n, val, v - 1, dp)
	return dp[n][v]

def count(n):
	if n < 3:
		return 0
	val = [3, 5, 10]
	v = len(val)
	dp = [[-1 for i in range(v + 2)] for i in range(n + 2)]
	a = solve(n, val, v, dp)
	return a


def solve(n, val, v):
	if n == 0:
		return 1
	if n < 0:
		return 0
	if v - 1 < 0:
		return 0
	if n >= val[v - 1]:
		return solve(n, val, v - 1) + solve(n - val[v - 1], val, v)
	else:
		return solve(n, val, v - 1)

def count(n):
	if n < 3:
		return 0
	val = [3, 5, 10]
	v = len(val)
	a = solve(n, val, v)
	return a


def count(n):
	arr = [3, 5, 10]
	t = [[1 if c == 0 else 0 for c in range(n + 1)] for r in range(4)]
	for i in range(1, 4):
		for j in range(1, n + 1):
			if arr[i - 1] <= j:
				t[i][j] = t[i - 1][j] + t[i][j - arr[i - 1]]
			else:
				t[i][j] = t[i - 1][j]
	return t[3][n]


def count(n):
	if n < 3:
		return 0
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(3, n + 1):
		dp[i] += dp[i - 3]
	for i in range(5, n + 1):
		dp[i] += dp[i - 5]
	for i in range(10, n + 1):
		dp[i] += dp[i - 10]
	return dp[n]


def count(n):

	def solve(i, n, arr):
		if n == 0:
			return 1
		if n < 0 or i == 3:
			return 0
		a = solve(i, n - arr[i], arr)
		b = solve(i + 1, n, arr)
		return a + b
	arr = [3, 5, 10]
	return solve(0, n, arr)


def count(n):
	points = [3, 5, 10]
	dp = [[0 for j in range(4)] for i in range(n + 1)]
	for j in range(4):
		dp[0][j] = 1
	for i in range(1, n + 1):
		for j in range(1, 4):
			if i - points[j - 1] >= 0:
				dp[i][j] = dp[i][j - 1] + dp[i - points[j - 1]][j]
			else:
				dp[i][j] = dp[i][j - 1]
	return dp[n][3]


def count(K):
	table = [[-1] * (K + 1) for _ in range(4)]

	def score(arr, n, K):
		if K == 0:
			return 1
		if n == 0 or K < 0:
			return 0
		if table[n][K] == -1:
			if arr[n - 1] > K:
				table[n][K] = score(arr, n - 1, K)
			else:
				table[n][K] = score(arr, n - 1, K) + score(arr, n, K - arr[n - 1])
		return table[n][K]
	return score([3, 5, 10], 3, K)


def count(n):

	class Solution:

		def __init__(self, Ans):
			self.Ans = Ans

		def recurr(self, idx, score):
			arr = [3, 5, 10]
			if score == 0:
				return 1
			if score < 0 or idx < 0:
				return 0
			if self.Ans[idx][score] != -1:
				return self.Ans[idx][score]
			f = self.recurr(idx, score - arr[idx])
			s = self.recurr(idx - 1, score)
			self.Ans[idx][score] = f + s
			return f + s
	Ans = []
	for i in range(0, 3):
		temp = [-1] * (n + 1)
		Ans.append(temp)
	obj = Solution(Ans)
	return obj.recurr(2, n)


def count(n):
	dp = [[0, 0, 0] for i in range(n + 1)]
	dp[0][0] = 1
	dp[0][1] = 1
	dp[0][2] = 1
	arr = [3, 5, 10]
	for i in range(1, n + 1):
		for j in range(3):
			if i - arr[j] >= 0:
				dp[i][j] = dp[i - arr[j]][j]
			if j >= 1:
				dp[i][j] += dp[i][j - 1]
	return dp[n][2]


moves = [3, 5, 10]
dp = [[-1] * 1001 for i in range(3)]

def solve(i, n):
	if n == 0:
		return 1
	if i == 3 or n < 0:
		return 0
	if dp[i][n] != -1:
		return dp[i][n]
	dp[i][n] = solve(i, n - moves[i]) + solve(i + 1, n)
	return dp[i][n]

def count(n):
	for i in range(3):
		for j in range(1001):
			dp[i][j] = -1
	ans = solve(0, n)
	return ans


def getTotalWays(CI, target, points, n, memo):
	if target == 0:
		return 1
	if CI == n:
		return 0
	currentKey = (CI, target)
	if currentKey in memo:
		return memo[currentKey]
	consider = 0
	if points[CI] <= target:
		consider = getTotalWays(CI, target - points[CI], points, n, memo)
	notConsider = getTotalWays(CI + 1, target, points, n, memo)
	ans = consider + notConsider
	memo[currentKey] = ans
	return ans

def count(n):
	points = [3, 5, 10]
	return getTotalWays(0, n, points, len(points), {})


def getTotalWays(CI, target, points, n):
	if target == 0:
		return 1
	if CI == n:
		return 0
	consider = 0
	if points[CI] <= target:
		consider = getTotalWays(CI, target - points[CI], points, n)
	notConsider = getTotalWays(CI + 1, target, points, n)
	return consider + notConsider

def count(n):
	points = [3, 5, 10]
	return getTotalWays(0, n, points, len(points))


def count(n):
	a = [3, 5, 10]
	n1 = len(a)
	tab = [[0] * (n + 1) for i in range(n1 + 1)]
	tab[0][0] = 1
	for i in range(1, n1 + 1):
		for j in range(n + 1):
			if a[i - 1] <= j:
				tab[i][j] = tab[i - 1][j] + tab[i][j - a[i - 1]]
			else:
				tab[i][j] = tab[i - 1][j]
	return tab[n1][n]


def count(n):
	dp = [[0 for i in range(3)] for i in range(n + 1)]
	a = [3, 5, 10]
	for i in range(3):
		dp[0][i] = 1
	for i in range(1, n + 1):
		for j in range(3):
			Pick = 0
			if i >= a[j]:
				Pick = dp[i - a[j]][j]
			Notpick = dp[i][j - 1]
			dp[i][j] = Pick + Notpick
	return dp[n][2]


from collections import defaultdict
scores = [3, 5, 10]

def recursion(index, score, memo):
	if score == 0:
		return 1
	if index > 2 or score < 0:
		return 0
	if (index, score) in memo:
		return memo[index, score]
	ans1 = recursion(index, score - scores[index], memo)
	ans2 = recursion(index + 1, score, memo)
	newsum = ans1 + ans2
	memo[index, score] = newsum
	return newsum

def count(n):
	memo = defaultdict(list)
	return recursion(0, n, memo)


from collections import Counter

def count(n):
	scores = Counter()
	scores[0] = 1
	d = Counter()
	for item in scores:
		i = 10
		while i <= n:
			d[item + i] += scores[item]
			i += 10
	for value in d:
		scores[value] += d[value]
	d = Counter()
	for item in scores:
		i = 5
		while i <= n:
			d[item + i] += scores[item]
			i += 5
	for value in d:
		scores[value] += d[value]
	d = Counter()
	for item in scores:
		i = 3
		while i <= n:
			d[item + i] += scores[item]
			i += 3
	for value in d:
		scores[value] += d[value]
	return scores[n]


def count(n):
	c = [3, 5, 10]
	dp = [0] * (n + 1)
	dp[0] = 1
	for coin in c:
		for amount in range(1, len(dp)):
			if coin <= amount:
				dp[amount] += dp[amount - coin]
	return dp[n]


import math

def count(n):
	t = [0] * (n + 1)
	t[0] = 1
	for i in range(3, n + 1):
		t[i] += t[i - 3]
	for i in range(5, n + 1):
		t[i] += t[i - 5]
	for i in range(10, n + 1):
		t[i] += t[i - 10]
	return t[n]


def count(n):

	def recursion(n, i):
		if n == 0:
			return 1
		if i < 0 or n < 0:
			return 0
		if dp[n][i] != -1:
			return dp[n][i]
		pick = 0
		if a[i] <= n:
			pick = recursion(n - a[i], i)
		notPick = recursion(n, i - 1)
		dp[n][i] = pick + notPick
		return dp[n][i]
	a = [3, 5, 10]
	dp = [[-1 for i in range(3)] for i in range(n + 1)]
	return recursion(n, 2)


def count(n):
	arr = [0, 3, 5, 10]
	dp = [[0 for y in range(n + 1)] for x in range(4)]
	for i in range(n + 1):
		dp[0][i] = 0
	for i in range(4):
		dp[i][0] = 1
	for i in range(1, 4):
		for j in range(1, n + 1):
			dp[i][j] = dp[i - 1][j]
			if j >= arr[i]:
				dp[i][j] += dp[i][j - arr[i]]
	return dp[3][n]


def count(n):
	a = [3, 5, 10]

	def recursion(a, i, n):
		if dp[n][i] != -1:
			return dp[n][i]
		if n == 0:
			return 1
		if i < 0 or n < 0:
			return 0
		NotPick = recursion(a, i - 1, n)
		Pick = 0
		if a[i] <= n:
			Pick = recursion(a, i, n - a[i])
		dp[n][i] = Pick + NotPick
		return dp[n][i]
	dp = [[-1 for i in range(3)] for i in range(n + 1)]
	return recursion(a, 2, n)


def findCombos(arr, i, N, W, memo):
	if i == N:
		return 0
	if W == 0:
		return 1
	curr = arr[i]
	key = (i, W)
	if key in memo:
		return memo[key]
	consider = 0
	if curr <= W:
		consider = findCombos(arr, i, N, W - curr, memo)
	notconsider = findCombos(arr, i + 1, N, W, memo)
	memo[key] = consider + notconsider
	return memo[key]

def count(n):
	options = [3, 5, 10]
	return findCombos(options, 0, 3, n, {})


import sys
sys.setrecursionlimit(10 ** 6)
scores = [3, 5, 10]

def rec2(mem, i, n):
	if n == 0:
		return 1
	if i == 3:
		return 0
	if (i, n) in mem:
		return mem[i, n]
	ans = 0
	if n >= scores[i]:
		ans = rec2(mem, i, n - scores[i])
	ans += rec2(mem, i + 1, n)
	mem[i, n] = ans
	return ans

def rec(i, n):
	if n == 0:
		return 1
	if i == 3:
		return 0
	dp = [[-1 for k in range(n + 1)] for i in range(4)]
	for k in range(0, n + 1):
		dp[3][k] = 0
	for i in range(3, -1, -1):
		dp[i][0] = 1
	for i in range(2, -1, -1):
		for k in range(0, n + 1):
			ans = 0
			if k >= scores[i]:
				ans = dp[i][k - scores[i]]
			ans += dp[i + 1][k]
			dp[i][k] = ans
	return dp[0][n]

def count(n):
	return rec(0, n)


import sys
sys.setrecursionlimit(10 ** 6)
scores = [3, 5, 10]

def rec(mem, i, n):
	if n == 0:
		return 1
	if i == 3:
		return 0
	if (i, n) in mem:
		return mem[i, n]
	ans = 0
	if n >= scores[i]:
		ans = rec(mem, i, n - scores[i])
	ans += rec(mem, i + 1, n)
	mem[i, n] = ans
	return ans

def count(n):
	mem = {}
	return rec(mem, 0, n)


def __helper(i, target, arr, dp):
	if target == 0:
		return 1
	if i == len(arr):
		return 0
	if dp[i][target] == None:
		dp[i][target] = 0
		if target - arr[i] >= 0:
			dp[i][target] = __helper(i + 1, target, arr, dp) + __helper(i, target - arr[i], arr, dp)
	return dp[i][target]

def count(n):
	arr = [3, 5, 10]
	dp = [[None for j in range(n + 1)] for i in range(3)]
	return __helper(0, n, arr, dp)


def count(n):
	ways = [3, 5, 10]
	return solve(ways, 3, n)

def solve(ways, n, target):
	if target == 0:
		return 1
	if n == 0:
		return 0
	if ways[n - 1] <= target:
		return solve(ways, n, target - ways[n - 1]) + solve(ways, n - 1, target)
	else:
		return solve(ways, n - 1, target)


def solve(n, dp):
	if n == 0:
		return 1
	if n < 0:
		return 0
	if dp[n] != -1:
		return dp[n]
	op1 = op2 = op3 = 0
	op1 = solve(n - 3, dp)
	op2 = solve(n - 5, dp)
	op3 = solve(n - 10, dp)
	dp[n] = op1 or op2 or op3
	return dp[n]

def count(n):
	dp = [0 for _ in range(n + 1)]
	dp[0] = 1
	ls = [3, 5, 10]
	for i in range(3):
		for j in range(ls[i], n + 1):
			dp[j] += dp[j - ls[i]]
	return dp[n]


def count(n):
	d = {}
	dp = {}
	arr = [3, 5, 10]

	def count(n, i):
		if n < 0 or i < 0:
			return 0
		if n == 0:
			return 1
		if arr[i] > n:
			return count(n, i - 1)
		else:
			return count(n - arr[i], i) + count(n, i - 1)
	return count(n, 2)


def count(n):
	dp = {}
	arr = [3, 5, 10]

	def count(n, i):
		if n < 0 or i < 0:
			return 0
		if n == 0:
			return 1
		if str(n) + str(i) in dp:
			return dp[str(n) + str(i)]
		if arr[i] > n:
			dp[str(n) + str(i)] = count(n, i - 1)
			return dp[str(n) + str(i)]
		else:
			dp[str(n) + str(i)] = count(n - arr[i], i) + count(n, i - 1)
			return dp[str(n) + str(i)]
	return count(n, 2)


def solve(n, dp, arr, i):
	if n == 0:
		return 1
	if n < 0 or i < 0:
		return 0
	if dp[n][i] != -1:
		return dp[n][i]
	a = solve(n - arr[i], dp, arr, i)
	b = solve(n, dp, arr, i - 1)
	dp[n][i] = a + b
	return dp[n][i]

def count(n):
	arr = [3, 5, 10]
	dp = [[-1 for j in range(3)] for i in range(n + 1)]
	return solve(n, dp, arr, 2)


def answer(i, target, arr, dp):
	if target == 0:
		return 1
	if i == 2:
		if target % arr[2] == 0:
			return 1
		else:
			return 0
	if dp[i][target] != -1:
		return dp[i][target]
	t1 = 0
	if arr[i] <= target:
		t1 = answer(i, target - arr[i], arr, dp)
	t2 = answer(i + 1, target, arr, dp)
	dp[i][target] = t1 + t2
	return dp[i][target]

def count(n):
	dp = [[-1 for x in range(n + 1)] for x in range(3)]
	return answer(0, n, [3, 5, 10], dp)


def count(n):
	nums = [3, 5, 10]
	dp = [[None for _ in range(n + 1)] for _ in range(4)]
	for i in range(4):
		for j in range(n + 1):
			if j == 0:
				dp[i][j] = 1
			elif i == 0:
				dp[i][j] = 0
			elif nums[i - 1] <= j:
				dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i - 1]]
			else:
				dp[i][j] = dp[i - 1][j]
	return dp[3][n]


def count(n):
	table = [0 for _ in range(n + 1)]
	table[0] = 1
	for i in range(3, n + 1):
		table[i] += table[i - 3]
	for i in range(5, n + 1):
		table[i] += table[i - 5]
	for i in range(10, n + 1):
		table[i] += table[i - 10]
	return table[n]


def count(n):
	dp = []
	for i in range(4):
		dp.append([-1] * (n + 1))
		dp[i][0] = 0
	arr = [3, 5, 10]
	for i in range(1, 4):
		for j in range(1, n + 1):
			if j - arr[i - 1] >= 0 and dp[i][j - arr[i - 1]] != -1:
				dp[i][j] = dp[i - 1][j] + dp[i][j - arr[i - 1]] + 1
			else:
				dp[i][j] = dp[i - 1][j]
	return dp[-1][-1] + 1


from collections import defaultdict

def count(n):
	hmap = defaultdict(int)
	hmap[0] = 1
	for i in range(1, n + 1):
		hmap[i] += hmap[i - 3]
	for i in range(1, n + 1):
		hmap[i] += hmap[i - 5]
	for i in range(1, n + 1):
		hmap[i] += hmap[i - 10]
	return hmap[n]


def count(n):
	arr = [3, 5, 10]
	t = [[0 for j in range(0, n + 1)] for i in range(0, len(arr) + 1)]
	for i in range(0, len(arr) + 1):
		for j in range(0, n + 1):
			if j == 0:
				t[i][j] = 1
			elif i == 0:
				t[i][j] = 0
			elif arr[i - 1] <= j:
				t[i][j] = t[i][j - arr[i - 1]] + t[i - 1][j]
			else:
				t[i][j] = t[i - 1][j]
	return t[3][n]


def count(n):
	scores = [3, 5, 10]
	dp = [[0 for i in range(n + 1)] for i in range(len(scores) + 1)]
	for i in range(len(scores) + 1):
		dp[i][0] = 1
	for i in range(1, len(scores) + 1):
		for j in range(1, n + 1):
			if j < scores[i - 1]:
				dp[i][j] = dp[i - 1][j]
			else:
				dp[i][j] = dp[i][j - scores[i - 1]] + dp[i - 1][j]
	return dp[len(scores)][n]