Why does the last element reflect the number of non-negative solutions?

Question

Please excuse my naivete as I don't have much programming experience. While googling something for an unrelated question, I stumbled upon this:

https://www.geeksforgeeks.org/find-number-of-solutions-of-a-linear-equation-of-n-variables/

I completely understand the first (extremely inefficient) bit of code. But the second:

def countSol(coeff, n, rhs): 

    # Create and initialize a table 
    # to store results of subproblems 
    dp = [0 for i in range(rhs + 1)] 
    dp[0] = 1

    # Fill table in bottom up manner 
    for i in range(n): 
        for j in range(coeff[i], rhs + 1): 
            dp[j] += dp[j - coeff[i]] 

    return dp[rhs]

confuses me. My question being: why does this second program count the number of non-negative integer solutions?

I have written out several examples, including the one given in the article, and I understand that it does indeed do this. And I understand how it is populating the list. But I don't understand exactly why this works.

Please excuse what must be, to some, an ignorant question. But I would quite like to understand the logic, as I think it rather clever that such a little snip-it is able able to answer a question as general as "How many non negative integer solutions exist" (for some general equation).

Answer 1

This algorithms is pretty cool and demonstrates the power of looking for a solution from a different perspective.

Let's take a example: 3x + 2y + z = 6, where LHS is the left hand side and RHS is the right hand side.

dp[k] will keep track of the number of unique ways to arrive at a RHS value of k by substituting non-negative integer values for LHS variables.

The i loop iterates over the variables in the LHS. The algorithm begins with setting all the variables to zero. So, the only possible k value is zero, hence

k        0   1   2   3   4   5   6 
dp[k] =  1   0   0   0   0   0   0

For i = 0, we will update dp to reflect what happens if x is 1 or 2. We don't care about x > 2 because the solutions are all non-negative and 3x would be too big. The j loop is responsible for updating dp and dp[k] gets incremented by dp[k - 3] because we can arrive at RHS value k by adding one copy of the coefficient 3 to k-3. The result is

k        0   1   2   3   4   5   6 
dp[k] =  1   0   0   1   0   0   1

Now the algorithm continues with i = 1, updating dp to reflect all possible RHS values where x is 0, 1, or 2 and y is 0, 1, 2, or 3. This time the j loop increments dp[k] by dp[k-2] because we can arrive at RHS value k by adding one copy of the coefficient 2 to k-2, resulting in

k        0   1   2   3   4   5   6 
dp[k] =  1   0   1   1   1   1   2

Finally, the algorithm incorporates z = 1, 2, 3, 4, 5, or 6, resulting in

k        0   1   2   3   4   5   6 
dp[k] =  1   1   2   3   4   5   7

In addition to computing the answer in pseudo-polynomial time, dp encodes the answer for every RHS <= the input right hand side.