Dice Combinations

coins = [1, 2, 3, 4, 5, 6]
value = []
first = []
count = []

# Break the problem into smaller problems (via momoization) and then find the solution.
def solve(x):
    if x < 0: return float("inf")
    if (x==0): return 0
    if value[x] != -1: return value[x]
    best = float("inf")
    for coin in coins:
        val = solve(x-coin)
        if (val != float("inf")): val += 1 # The plus one basically coint for the amount of coins
        best = min(best, val)
        if x-coin >= 0: first[x] = coin # This gives you the first coin for each sum of money
    value[x] = best
    return best

def getCoins(x):
    global first, value
    for i in range(1, x):
        value[i] = float("inf")
        for c in coins:
            if i-c >=0 and value[i-c] + 1 < value[i]:
                value[i] = value[i-c] + 1
                first[i] = c

# Counts the amount of solutions, everytime you can add a coin, you can add one to the amount of the previous count
def CountSolutions(i):
    for x in range(1, i + 1):
        for c in coins:
            if (x-c >= 0): 
                count[x] += count[x-c]
                count[x] %= (10**9 + 7)

# This is basically a memory that stores a set of values that have been solved to then easily reuse them later when looking for all solutions
def BuildMemoization(x):
    global value, first, count
    value = [-1 for _ in range(x + 1)]
    first = [-1 for _ in range(x + 1)]
    count = [0 for _ in range(x + 1)]
    value[0] = 0
    first[0] = 0
    count[0] = 1
    for i in range(1, x): solve(i)

def amountOfSolutions(x):
    BuildMemoization(x)
    CountSolutions(x)
    print(count[x])

amountOfSolutions(int(input()))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED