CSES 1636有序硬币组合II递归解法超时优化咨询

题目描述 #

现有包含n种面值均为正整数的硬币的货币系统，你的任务是计算凑出总金额x的不同有序方案总数。
例如，若硬币为{2,3,5}、目标金额为9，共有3种方案：

2+2+5
3+3+3
2+2+2+3

原代码问题分析 #

原递归记忆化代码逻辑正确，超时主要由以下原因导致：

• 输入效率低：默认cin开启了与stdio的同步，输入速度慢
• 冗余递归调用：未判断当前硬币面值是否超过剩余目标金额，产生大量无意义递归调用
• 存在溢出风险：两个取模后的值直接相加可能超出32位int范围，未做类型转换
• 重复取模开销：多次调用取模运算增加不必要的计算量

优化方案 #

核心优化点 #

1. 输入加速：关闭cin同步并解绑流，将输入速度提升至和scanf相当的水平
2. 剪枝优化：提前将硬币按升序排序，当当前硬币面值大于剩余目标金额时直接返回0（后续硬币面值更大，不可能满足需求），大幅减少无效递归
3. 溢出规避：相加时先转为long long类型，最后统一取模，既避免整数溢出也减少取模次数
4. 调用开销优化：将递归函数声明为inline，降低函数调用的额外开销

优化后可通过评测的代码 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int M = 1000000007;
 
vector<int> arr;
vector<vector<int>> dp;

inline int solve(int i, int target) {
    if (target == 0) return 1;
    if (i >= (int)arr.size() || arr[i] > target) return 0;
    if (dp[i][target] != -1) return dp[i][target];
    return dp[i][target] = (1LL * solve(i, target - arr[i]) + solve(i + 1, target)) % M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, target;
    cin >> n >> target;
    arr.resize(n);
    dp.resize(n + 1, vector<int>(target + 1, -1));
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    cout << solve(0, target);
    return 0;
}

内容的提问来源于stack exchange，提问作者dy123