如何计算与[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＆lt; = 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），对应于sum s的组合数，最大数字等于或小于> D。

然后，我们可以使用递归关系的

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

第一项f（s，d-1）对应于所有术语较少或等于d-1的组合，第二个术语f（SD，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，该解决方案大约在10 ms中提供。

#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;
}