使用 (1,...,K) 找出加到 N 上的可能总和数

Question

我有以下问题要解决：给定一个数 N 和 1<=k<=N，计算 (1,...,k) 与 N 相加的可能和数。可能有相等的因子（例如，如果 N=3 和 k=2，(1,1,1) 是一个有效的总和），但是 不能计算排列（例如，如果 N=3 和k=2，将 (1,2) 和 (2,1) 算作一个解）。我已经实现了下面的递归 Python 代码，但我想找到一个更好的解决方案（也许使用动态编程？）。它看起来类似于 triple step problem，但具有不计算排列的额外限制。

    
def find_num_sums_aux(n, min_k, max_k):
    
    # base case
    if n == 0:
        return 1
    
    count = 0
    # due to lower bound min_k, we evaluate only ordered solutions and prevent permutations
    for i in range(min_k, max_k+1):
        if n-i>=0:
            count += find_num_sums_aux(n-i, i, max_k)
    return count

def find_num_sums(n, k):
    count = find_num_sums_aux(n,1,k)
    return count

Answer 1

这是动态规划中的标准问题（子集和问题）。

让我们定义函数 f(i,j)，它给出了使用数字子集 (1...i) 获得和 j 的方法的数量，那么您的问题的结果将是 f (k,n).

对于范围 (1...i) 中的每个数字 x，x 可能是总和 j 的一部分，也可能不是，所以我们需要计算这两种可能性。

注意： f(i,0) = 1 for any i，这意味着你可以通过一种方式得到 sum = 0 这种方式是不采取任何范围 (1...i).

中的数字

这是用 C++ 编写的代码：

   

     int n = 10;
        int k = 7;
        int f[8][11];
        
        //initializing the array with zeroes
        for (int i = 0; i <= k; i++)
            for (int j = 0; j <= n; j++)
                f[i][j] = 0;
    
        f[0][0] = 1;
    
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j <= n; j++) {
                if (j == 0)
                    f[i][j] = 1;
                else {
                    f[i][j] = f[i - 1][j];//without adding i to the sum j
                    if (j - i >= 0)
                        f[i][j] = f[i][j] + f[i - 1][j - i];//adding i to the sum j
                }
            }
        }   
        
        cout << f[k][n] << endl;//print f(k,n)

更新
要处理我们可以重复元素的情况，例如 (1,1,1) 将得到总和 3，您只需要通过更改以下代码行允许多次选取相同的元素：

f[i][j] = f[i][j] + f[i - 1][j - i];//adding i to the sum

为此：

f[i][j] = f[i][j] + f[i][j - i];

使用 (1,...,K) 找出加到 N 上的可能总和数

Find the number of possible sums which add to N using (1,...,K)

recursion

dynamic-programming

coin-change