递归多线程求解有序序列和：报错修复与算法优化咨询

一、即时崩溃问题修复 #

你的代码崩溃核心原因是错误使用std::vector::reserve：
reserve(DIM)仅为向量预分配内存空间，但不会创建任何元素，此时向量th的实际大小仍为0。直接通过th[i]赋值线程会触发越界访问，导致未定义行为（表现为terminate called错误）。

修复后的多线程代码片段 #

将线程创建逻辑改为emplace_back（直接在向量内构造线程对象）：

// 替换原线程创建循环
for(i=0; i<DIM; i++)
    th.emplace_back(sub, in - val[i], &psum[i], level+1);

但即使修复此问题，递归式多线程仍不可行：每一层递归都会生成DIM个线程，对于NUM=30会产生指数级数量的线程，导致系统资源耗尽，最终仍会崩溃或性能极差。

二、高效算法替代：动态规划 #

此问题属于有序无界组合计数，适合用动态规划（DP）解决，时间复杂度为O(NUM * DIM)，即使DIM=20、NUM=300也能瞬间完成计算。

算法思路 #

1. 定义dp[n]：表示和为n的有序序列数量
2. 基础状态：dp[0] = 1（空序列是唯一和为0的情况）
3. 状态转移：对于每个n，遍历所有集合元素val[i]，若n >= val[i]，则dp[n] += dp[n - val[i]]（相当于将val[i]追加到所有和为n-val[i]的序列末尾）

完整DP代码 #

#include <iostream>
#include <vector>

#define DIM     8
#define NUM     30

long val[DIM] = {1,2,3,5,7,11,14,23};

int main() {
    // 使用long long避免大数溢出
    std::vector<long long> dp(NUM + 1, 0);
    dp[0] = 1; // 基础状态

    for (int n = 1; n <= NUM; ++n) {
        for (int i = 0; i < DIM; ++i) {
            if (n >= val[i]) {
                dp[n] += dp[n - val[i]];
            }
        }
    }

    std::cout << dp[NUM] << std::endl;
    return 0;
}

验证示例 #

当NUM=3时，计算得dp[3] = 4，与你给出的正确结果一致。

三、额外优化建议 #

1. 数据类型选择：必须用long long存储结果，否则对于NUM=300这类较大值会发生整数溢出。
2. 并行化（可选）：若需进一步加速，可将DP的外层循环（n的遍历）拆分为多个线程处理不同区间，但对于NUM=300来说，单线程已足够高效。
3. 元素预处理：若集合中有大于NUM的元素（如DIM=16中的301），可提前过滤，减少无效计算。

内容的提问来源于stack exchange，提问作者Kay K.