Find the total number of ways W, in which a sum S can be reached in N throws of a dice

I was solving this question:

Given there is a 6 sided dice. Find the total number of ways W, in which a sum S can be reached in N throws.


Example:


S = 1, N = 6 => W = 0


S = 6, N = 6 => W = 1


S = 7, N = 6 => W = 6


S = 3, N = 2 => W = 2

How to improve its complexity and make it more readable?

def get_sum_dp(n,s):
    t = [[0 for i in xrange(1,s+2)] for j in xrange(1,n+2)]
    for j in xrange(1,7):
        t[1][j] = 1
    for i in range(2, n+1):
        for j in range(1, s+1):
            for k in range(1,7):
                if k < j:
                    t[i][j] += t[i-1][j-k]
    print t[n][s]    

get_sum_dp(2,8)

1. Review

-
The sum \$s=0\$ can be reached in \$n=0\$ throws in exactly one way, but:

>>> get_sum_dp(0, 0)
Traceback (most recent call last):
  File "", line 1, in 
  File "cr161002.py", line 32, in get_sum_dp
    t[1][j] = 1
IndexError: list index out of range

-
The name get_sum_dp could be clearer (what does "dp" mean? dynamic programming?). I would use a name like dice_rolls.

-
A docstring would be helpful in understanding what the function does.

-
It's usually more convenient to return a result instead of printing it. This would allow the result to be used in other computations if needed.

-
Instead of

t = [[0 for i in xrange(1,s+2)] for j in xrange(1,n+2)]

you could write:

t = [[0] * (s + 1) for _ in xrange(n + 1)]

(It's conventional to use _ for a loop variable whose value is not used.)

-
The initial condition is:

for j in xrange(1,7):
    t[1][j] = 1

but it would be simpler to use the following initial condition:

t[0][0] = 1

and change:

for i in range(2, n+1):
    for j in range(1, s+1):
        if k < j:

to:

for i in range(1, n+1):
    for j in range(1, s+1):
        if k <= j:

(This also fixes the bug I noted in point 1 above.)

-
In the nested loops:

for i in range(2, n+1):
    for j in range(1, s+1):

the loop over j goes all the way from 1 to s. But some of this may be wasted, because the sum of i dice must be between i and i * 6. So you could reduce the amount of work by writing:

for i in range(2, n+1):
    for j in range(i, min(s, i * 6) + 1):

-
Similarly, instead of checking k on every loop iteration:

for k in range(1,7):
    if k < j:
        t[i][j] += t[i-1][j-k]

you could compute the loop bounds in advance:

for k in xrange(1, min(6, j) + 1):
     t[i][j] += t[i - 1][j - k]

1. Revised code

def dice_rolls(n, s):
    """Return the number of ways in which a sum s can be reached in n
    throws of a 6-sided die.
    """
    t = [[0] * (s + 1) for _ in xrange(n + 1)]
    t[0][0] = 1
    for i in xrange(1, n + 1):
        for j in xrange(i, min(s, i * 6) + 1):
            for k in xrange(1, min(6, j) + 1):
                t[i][j] += t[i - 1][j - k]
    return t[n][s]

1. Alternative approach

Dynamic programming builds up a table of solutions to sub-problems from the bottom up (starting with small problems and using those to solve larger problems). But an alternative approach works from the top down, using recursion to compute the sub-problems, and memoization to avoid duplicated work. This often results in clearer code and it is easier to compute only the table entries that you need.

In Python 3.2 or later, you can easily memoize a function using the @functools.lru_cache decorator, like this:

import functools

@functools.lru_cache(maxsize=None)
def dice_rolls(n, s):
    """Return the number of ways in which a sum s can be reached in n
    throws of a 6-sided die.
    """
    if s  n * 6:
        return 0
    elif n == s == 0:
        return 1
    else:
        return sum(dice_rolls(n - 1, s - i) for i in range(1, 7))

(Python 2.7 lacks functools.lru_cache, but there's a backport package.)

StackExchange Code Review Q#161002, answer score: 14