algorithm - 查找数字和的所有变体

Question

谁能告诉我一个算法/公式，说明如何计算具有特定上限的数字和的所有变化

例如，如果我的数字总和是 6，上限是 123，那么该数字总和的所有变化将是:6、15、24、33、42、51、60、105、114 和 123。

上限可以达到 10**18 并且程序需要在 1 秒内运行(在 C/CPP 中)，所以暴力破解不是一种选择。

Answer 1

我认为有一种递归方法可以解决这个问题:考虑一个过程 int f(bool limit, int bit_count, int bit_sum) , 它计算不超过 bit_count 的变体数量位和为 bit_sum 的位. bool参数limit表示限制(在您的示例中为 123)是否生效。

假设 Limit[i]表示极限的第 i 位。

int f(bool limit, int bit_count, int bit_sum){
    if(bit_sum < 0)
        return 0;
    if(bit_count == -1)
        if(bit_sum == 0)
            return 1;
        else
            return 0;

    int ans = 0;
    for(int i = 0; i <= limit ? Limit[bit_count] : 9; i++){
        ans += f(limit && i == Limit[bit_count], bit_count - 1, bit_sum - i);
    }
    return ans;
}

在您的位和为 6 且上限为 123 的示例中，Limit[2] = 1 , Limit[1] = 2 , Limit[0] = 3 .答案是f(true, 2, 6) .

为了快速起见，可以通过记录表将这种递归的方式转化为动态规划的方式。对应DP方法的时间复杂度为O(bit_sum * log(upper_limit)) .我觉得这个速度可以满足你1秒的要求。