pythoncombinationsdynamic-programmingdice

Anyway to make this code goes faster in python?

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

MOD = 1000000007
dp = [0] * 1000001

def DP(dp, left):
    if(dp[left] != 0):
        return dp[left]
    for i in range(1, 7):
        if(left - i >= 0):
            dp[left] += DP(dp, left - i)
            dp[left] %= MOD
    return dp[left]

n = int(input())
dp[0] = 1
print(DP(dp, n))

Is there anyway to make this code goes faster? It can run when n is around 100000 but it was slowdown when n=654321. The task is to count the way to combining 1, 2, 3, 4, 5, 6 (a dice's faces) to make n. Example: when n=3, all the way to create n is 4: 1+1+1; 2+1; 1+2; 3. I was trying to use Dynamic Programming skill to solve but timeout. Thanks for your help!

Solution

  • The inner loop can be optimized by using a prefix sums. A list of numbers with list length of n+1 to store the prefix sums.

    def DP(n):
    MOD = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n+1):
        for j in range(1, min(i, 6) + 1):
            dp[i] = (dp[i] + dp[i-j]) % MOD
    return dp[n]

int(input())
print(DP(n))