0
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!

Vudo
  • 13
  • 6
  • "I was trying to use Dynamic Programming skill to solve" - in your own words, what do you think "dynamic programming" means, and what part of the program represents your attempt to do this? How would the program be different, if you were *not* "trying to use Dynamic Programming skill"? – Karl Knechtel Jun 12 '23 at 06:33
  • Hint: where the code says `dp = [0] * 1000001`, what do you think is the purpose of creating this list? If you want to use "dynamic programming", when you get to the divide-and-conquer step in the algorithm, should the code make a recursive call? Or should it use a value that it already "knows" and has stored in the list? Therefore, what needs to happen first - the calculation for the larger value of `n`, or the calculation for the smaller value of `n`? Other than making recursive calls, can you think of a way to change the program, so that results for small values of `n` are computed first? – Karl Knechtel Jun 12 '23 at 06:37
  • @KarlKnechtel Not sure how to interpret your comments/closing. Are you saying they're not using dynamic programming? – Kelly Bundy Jun 12 '23 at 07:35
  • How much too slow is it? – Kelly Bundy Jun 12 '23 at 07:54
  • @KarlKnechtel sorry for the mistake, I was about to say "to use my Dynamic Programming skill to solve". In my opinion, I think dynamic programming is a way to store all the last result to reuse them again. Example all the way to create n when n=4: 1+1+1+1 (store the list); 2+1+1 (reuse the list and calculating the first 1+1, store the list also); 2+2 (reuse the recently list that we stored); 3+1 (the sum of 2+1 in the list 2+1+1 with the last +1)... – Vudo Jun 12 '23 at 07:55
  • @KellyBundy about over 4 sec but the testing system required only 1 sec – Vudo Jun 12 '23 at 07:57
  • Is the accepted answer fast enough? It's only ~3 times faster than yours in my testing. By **actually** using something like prefix sums, I have a solution ~20 times faster than yours. (And a different approach might still be a lot faster but it's annoying to implement so I didn't). – Kelly Bundy Jun 12 '23 at 08:13
  • @KellyBundy yeah it slow in python3 but it goes really fast in pypy3. – Vudo Jun 12 '23 at 08:16
  • @KellyBundy "Are you saying they're not using dynamic programming?" - yes, that was my conclusion from the fact that there is a recursive call, rather than a lookup into previously calculated results. – Karl Knechtel Jun 12 '23 at 08:36
  • @KarlKnechtel But the very first thing each call does is a lookup (and likely return) of a previously calculated result. Standard memoization, and a form of dynamic programming... – Kelly Bundy Jun 12 '23 at 08:41

2 Answers2

0

Lets try to use a bottom-up, tabulation method, we iteratively compute the values for smaller problems first and then use these values to compute the value.

def DP(n):
    MOD = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(1, n+1):
        for j in range(1, 7):
            if i >= j:
                dp[i] += dp[i - j]
                dp[i] %= MOD
    return dp[n]

n = int(input())
print(DP(n))
Saxtheowl
  • 4,136
  • 5
  • 23
  • 32
0

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))
yoonghm
  • 4,198
  • 1
  • 32
  • 48