Given a list of positive integers $(x_0,…,x_n)$ and a positive integer $m$, how many non-negative integer tuples $(v_0,…,v_n)$ are there so that

Let $P(x_0,..x_n, m)$ denote the solution to the above problem. In the simplest case, let $n=0$, then $P(x_0, m) = 0, 1$, depending on if $m$ is a multiple of $x_0$. In the next simplest case, let $n=1$, then

where $k_1 \in \mathbb{Z}$ such that $m - k_1x_1 >= 0$ and $m - (k_1 +1)x_1 < 0$.

This probably reminds you of dynamic programming, in which we bootstrap the solution from solutions of subproblems.

In this case we will build a 2d dp table such that

The update rule for this dp table is precisely eq 1.

Let’s put it into python

def num_tuples(nums: List, m:int) -> int:
    '''
    nums: a list of positive integers
    m: a positive integer

    Return: number of ways to use elements of nums with repetition to sum up to m
    '''
    n = len(nums)
    dp = [[0 for _ in range(m+1)] for _ in range(len(n))]
    
    # base case
    for j in range(m+1):
        if float(j) % nums[0] == 0:
            dp[1][j] = 1

    for i in range(1, n+1):
        for j in range(m+1):
            # use previous solution
            k = 0
            while nums[i-1]*k <= j:
                dp[i][j] += dp[i-1][j-k*nums[i-1]]
                k+=1
    return dp[n][m]

This algothrithm is $O(nmm)$, it is not easy to scale. How can we improve on it?

For all dynamic programming question, one should be able to write down a functional equation as the bootstraping rule. In the above solution, our functional equation is

But

In our dp table, when computing $dp[i][j] = p(x_0,…,x_{i-1}, j)$ we have in fact computed $dp[i][j-x_{i-1}] = p(x_0,…,x_{i-1}, j - x_{i-1})$. Instead of using it, we choose to only to use info from $dp[i-1][:]$, that is where the inefficiency comes in.

To recap, we update the dp table by $dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]$

Here is how to fix it

def num_tuples(nums: List, m:int) -> int:
    '''
    nums: a list of positive integers
    m: a positive integer

    Return: number of ways to use elements of nums with repetition to sum up to m
    '''
    n = len(nums)
    dp = [[0 for _ in range(m+1)] for _ in range(len(n))]
    
    # base case
    for j in range(m+1):
        if float(j) % nums[0] == 0:
            dp[1][j] = 1

    for i in range(1, n+1):
        for j in range(m+1):
            dp[i][j] = dp[i-1][j]

            if coins[i-1] <= j:
                dp[i][j] += dp[i][j - coins[i-1]]

    return dp[n][m]