为什么最后一个元素反映了非负解的数量?

 收藏

请原谅我天真,因为我没有太多的编程经验。在搜寻一个无关的问题时,我偶然发现:

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]

使我困惑。我的问题是:第二个程序为什么要计算非负整数解的数量?

我已经写了几个示例,包括文章中给出的示例,并且我知道它确实可以做到这一点。而且我了解它是如何填充列表的。但是我不明白为什么会这样。

在某些情况下,请原谅什么是一个无知的问题。但是,我很想了解逻辑,因为我认为这样一个小巧的剪裁相当聪明,它能够回答一个普遍的问题,例如“存在多少非负整数解”(对于某些一般方程式)。

回复