如何计算 [1, N] 的组合数使组合和等于 N？

Question

when n = 1
S(1) = 1;

when n = 2, there are two combinations
2 = 2
2 = 1 + 1
S(2) = 2;

when n = 3, there are 3
3 = 3
3 = 1 + 1 + 1
3 = 1 + 2
S(3) = 3

4 = 4
4 = 1 + 1 + 1 + 1
4 = 2 + 1 + 1
4 = 2 + 2
4 = 3 + 1
S(4) = 5

…………

n <= 1000，如何计算S(n)？我想出了一个强力 dfs 解决方案，这里是 python:

中的代码

class S1:
    def __init__(self):
        self.cnt = 1

    def dfs(self, begin, n, remain):
        if n == 1: return
        if remain == 0:
            self.cnt += 1
            return 
        if remain < 0:
            return 
        for i in range(begin, n):
            self.dfs(i, n, remain - i)

是否有其他一些不使用递归且时间复杂度更小的方法？

Answer 1

一个解决方案在于定义一个函数f(s, d)，对应于总和s的组合数，最大位数等于或小于d。

那么，我们可以使用递归关系

f(s, d) = f(s, d-1) + f(s-d, d)

第一项f(s, d-1)对应所有项小于或等于d-1的组合，第二项f(s-d, d)对应至少一个元素等于的情况d.

必须注意一些特殊值：

 f(s, 1) = 1
 if (d > s) then f(s, d) = f(s, s)
 f(0,d) = 1

这可以通过迭代的方式实现。这可以用递归的方式等效地实现。但是，在后一种情况下，重要的是使用记忆以避免多次计算相同的值。

最终答案等于

 S(n) = f(n, n)

总复杂度为 O(n^2)，这应该足以满足最大尺寸 n = 1000。

下面是一个 C++ 实现来说明该算法。以n = 1000为例，10ms左右给出解。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

std::string toString(__int128 num) {
    auto neg = num < 0;
    if (neg) num = -num;
    std::string str;
    do {
        int digit = num % 10;
        str += std::to_string(digit);
        num /= 10;
    } while (num != 0);
    std::string rev;
    if (neg) rev = "-" + std::string (str.rbegin(), str.rend());
    else rev = std::string (str.rbegin(), str.rend());
    return rev;
}

int main() {
    std::cout << "enter n: ";
    int n;
    std::cin >> n;
    std::vector<std::vector<__int128>> sums (n+1, std::vector<__int128> (n+1));
    
    for (int d = 0; d <= n; d++) {
        sums[0][d] = 1;
    }
    for (int sum = 1; sum <= n; sum++) {
        sums[sum][1] = 1;
        for (int d = 2; d <= sum; d++) {
            int dp = std::min (sum-d, d);
            sums[sum][d] = sums[sum][d-1] + sums[sum-d][dp];
        }
    }
    std::cout << "S[" << n << "]= " << toString(sums[n][n]) << "\n";
    return 0;
}

如何计算 [1, N] 的组合数使组合和等于 N？

How to compute the number of combinations with [1, N] that makes the combination sum equals to N?

algorithm

combinations