n个变量的线性方程的解的个数

Question

// A Dynamic programming based C++ program to find number of
// non-negative solutions for a given linear equation
#include<bits/stdc++.h>
using namespace std;

// Returns counr of solutions for given rhs and coefficients
// coeff[0..n-1]
int countSol(int coeff[], int n, int rhs)
{
    // Create and initialize a table to store results of
    // subproblems
    int dp[rhs+1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;

    // Fill table in bottom up manner
    for (int i=0; i<n; i++)
      for (int j=coeff[i]; j<=rhs; j++)
         dp[j] += dp[j-coeff[i]];

    return dp[rhs];
}

// Driver program
int main()
{
    int coeff[]  = {2, 2, 5};
    int rhs = 4;
    int n = sizeof(coeff)/sizeof(coeff[0]);
    cout << countSol(coeff, n, rhs);
    return 0;
}

我是竞争性编程的新手，我只是偶然发现了这段代码。我想知道这个特定片段背后的直觉，就像第二个for循环如何帮助。谢谢。

   // Fill table in bottom up manner
        for (int i=0; i<n; i++)
          for (int j=coeff[i]; j<=rhs; j++)
             dp[j] += dp[j-coeff[i]];

这是使用自下而上的方法，假设j= 3和j-coeff[i] = 2

那么d[3] = d[3] + d[2]如何给出解决方案？如何简单地添加先前结果和当前结果可以得到线性变量的整体解？

Answer 1

想象一下，你有无限数量的硬币价值2,3,5（你的coeff[]），你想知道解决方案的数量，使一些总和形式给硬币设置。

在第一次循环运行时，您将用硬币2填充表格。表格将被填充

idx    0  1  2  3  4  5  6
num    1  0  1  0  1  0  1 

因为有唯一的方法可以得到这些硬币。

在第二次循环运行时，你用硬币3填充表格 - 现在你将有可能由硬币2和3组成的总和

idx    0  1  2  3  4  5  6
num    1  0  1  1  1  1  2

请注意，单元格5填充2 + 3 - 类似于您的问题情况，单元格6现在包含2个变体：2 + 2 + 2和3 + 3