为什么最后一个元素反映的是非负解的个数？

Question

请原谅我的天真，因为我没有太多的编程经验。在谷歌搜索一个不相关的问题时，我偶然发现了这个：

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

我完全理解了第一段（效率极低的）代码。但是第二个：

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]

让我很困惑。我的问题是：为什么第二个程序要计算非负整数解的数量？

我已经写了几个例子，包括文章中给出的那个，我知道它确实是这样做的。我了解它是如何填充列表的。但我不明白 为什么会这样。

请原谅这个对某些人来说肯定是无知的问题。但我很想理解其中的逻辑，因为我认为这样一个小片段相当聪明——它能够回答像 "How many non negative integer solutions exist" 这样一般的问题（对于一些一般方程）。

Answer 1

这个算法很酷，展示了从不同角度寻找解决方案的力量。

举个例子：3x + 2y + z = 6，其中LHS是左边，RHS是右边。

dp[k] 将通过用非负整数值替换 LHS 变量来跟踪获得 RHS 值 k 的独特方法的数量。

i 循环遍历 LHS 中的变量。该算法从将所有变量设置为零开始。因此，唯一可能的 k 值为零，因此

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

对于 i = 0，我们将更新 dp 以反映如果 x 是 1 或 2 会发生什么。我们不关心 x > 2，因为解都是非-negative 和 3x 太大了。 j 循环负责更新 dp 并且 dp[k] 增加 dp[k - 3] 因为我们可以通过添加系数 k 的一个副本来得到 RHS 值 k =26=] 到 k-3。结果是

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

现在算法继续 i = 1，更新 dp 以反映所有可能的 RHS 值，其中 x 是 0、1 或 2，y 是 0、1、2 或 3。这时间 j 循环将 dp[k] 递增 dp[k-2] 因为我们可以通过将系数 2 的一个副本添加到 k-2 来得到 RHS 值 k , 结果

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

最后，该算法结合了 z = 1、2、3、4、5 或 6，结果是

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

除了在伪多项式时间内计算答案外，dp 还对每个 RHS <= 输入右侧的答案进行编码。

为什么最后一个元素反映的是非负解的个数？

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

python

bottom-up