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

Question

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

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

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

Answer 1

创建一个基于 DP 的解决方案来计算最多为 n 的 k 位数字的总和。

F(k,n) = sum_i F(k-1, ni)

假设您的最大值有 k 位，最高有效位是 sig(max)，dropsig(max) 是没有最高有效位的数字。

G(k,max,n) = F(k-1, n)+ G(k-1, dropig(max), n-sig(max) ) + sum_i (k-1, ni) 对于 i = 1 到信号（最大）-1。

显然，您必须处理极端情况。但这里是总结。

第一个组件对应于数字长度小于最大数字长度的情况。

第二个分量对应于解的最高有效位与最大值的最高有效位相同的情况。

第三个分量对应于解的最高有效位小于最大值的有效位但大于或等于 1 的情况。

Answer 2

我认为有一种递归方法可以解决这个问题：考虑一个过程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秒的要求。