algorithm - 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