确实，有一种方法可以证明这种模式经常起作用。如果它们的数量相当小，它也可以用于枚举具有给定属性的所有X。您甚至可以使用它来聚合具有给定属性的所有X上的某些关联运算符，例如查找其总和。

为了理解一般思想，让我们尝试用X和Y
的十进制表示形式来表达条件X≤Y。

假设我们有X = x 1 x 2 … x n-1 x n_和Y = _y 1 y 2 … y n-1 y n，其中 _x i_和 _y
i_是X和Y的十进制数字。如果数字的长度不同，我们总是可以在较短的数字前面加上零数字。

让我们定义leftmost_lo为最小的 我 用 X 我 leftmost_lo为 _n +1_ 。类似地，我们定义为最小的 _我_ 与 _X_ _我_ _ >ÿ __我 ，或 N + 1 ，否则。 leftmost_hi

现在X≤Y为true，如果且恰好为leftmost_lo <=leftmost_hi。有了这种观察，就可以对问题应用一种动态编程方法，从而将X的数字一个接一个地“设置”。我将用您的示例问题来证明这一点：

计算具有属性X≤Y且X的数字总和为60的整数X的数量f（Y）

让n是个Y的位数和y[i]是 我 的Y根据上述定义个十进制数字。以下递归算法解决了该问题：

count(i, sum_so_far, leftmost_lo, leftmost_hi):
    if i == n + 1:
        # base case of the recursion, we have recursed beyond the last digit
        # now we check whether the number X we built is a valid solution
        if sum_so_far == 60 and leftmost_lo <= leftmost_hi:
            return 1
        else: 
            return 0
    result = 0
    # we need to decide which digit to use for x[i]
    for d := 0 to 9
        leftmost_lo' = leftmost_lo
        leftmost_hi' = leftmost_hi
        if d < y[i] and i < leftmost_lo': leftmost_lo' = i
        if d > y[i] and i < leftmost_hi': leftmost_hi' = i
        result += count(i + 1, sum_so_far + d, leftmost_lo', leftmost_hi')
    return result

现在我们已经f(Y) = count(1, 0, n + 1, n + 1)解决了问题。我们可以将备忘录添加到功能中以使其快速。对于此特定实现，运行时为
O（n 4）。实际上，我们可以巧妙地优化该想法，使其变为 O（n）
。这是作为练习留给读者（提示：您可以压缩存储在信息leftmost_lo和leftmost_hi到单个位，你可以修剪如果sum_so_far > 60）。该解决方案可以在本文结尾处找到。

如果仔细观察，sum_so_far这只是一个任意函数的示例，该函数从X的数字序列中计算一个值。它可以是 任何
可以逐位计算并输出足够小的结果的函数。它可能是数字的乘积，满足特定属性或许多其他事情的一组数字的位掩码。

它也可以是返回1或0的函数，具体取决于数字是否仅由数字4和7组成，这可以轻松地解决第二个示例。我们要小心一点，因为在这里我们 是
允许在一开始就具有前导零，所以我们需要进行通过递归函数调用告诉我们是否仍然允许使用零作为一个数字的附加位。

计算X≤Y并且X是回文的整数X的数量f（Y）

这一点要难一些。我们需要注意前导零：回文数的镜像点取决于我们有多少个前导零，因此我们需要跟踪前导零的数量。

但是，有一个技巧可以简化它：如果我们可以对 f（Y）
进行计数，并附加限制，即所有数字X必须具有与Y相同的数字计数，那么我们也可以通过迭代遍历来解决原始问题所有可能的数字计数并累加结果。

因此，我们可以假设我们根本没有前导零：

count(i, leftmost_lo, leftmost_hi):
    if i == ceil(n/2) + 1: # we stop after we have placed one half of the number
        if leftmost_lo <= leftmost_hi:
            return 1
        else: 
            return 0
    result = 0
    start = (i == 1) ? 1 : 0    # no leading zero, remember?
    for d := start to 9
        leftmost_lo' = leftmost_lo
        leftmost_hi' = leftmost_hi
        # digit n - i + 1 is the mirrored place of index i, so we place both at 
        # the same time here
        if d < y[i]     and i     < leftmost_lo': leftmost_lo' = i
        if d < y[n-i+1] and n-i+1 < leftmost_lo': leftmost_lo' = n-i+1
        if d > y[i]     and i     < leftmost_hi': leftmost_hi' = i
        if d > y[n-i+1] and n-i+1 < leftmost_hi': leftmost_hi' = n-i+1
        result += count(i + 1, leftmost_lo', leftmost_hi')
    return result

结果将再次是f(Y) = count(1, n + 1, n + 1)。

更新： 如果我们不仅要计算数字，还可能要枚举它们或从中计算一些不公开组结构的聚合函数，则在递归过程中，我们还需要在X上施加下限。这增加了一些参数。

更新2： O（n）“数字和60”示例的解决方案：

在此应用程序中，我们从左到右放置数字。由于我们只对是否leftmost_lo < leftmost_hi成立感兴趣，因此让我们添加一个新参数lo。loiif为true leftmost_lo < i，否则为false。如果lo为true，则可以使用position的任何数字i。如果为假，则只能使用数字0到Y
[i]，因为任何较大的数字都将导致leftmost_hi = i < leftmost_lo并且因此无法导致解决方案。码：

def f(i, sum_so_far, lo):
    if i == n + 1: return sum_so_far == 60
    if sum_so_far > 60: return 0
    res = 0
    for d := 0 to (lo ? 9 : y[i]):
         res += f(i + 1, sum + d, lo || d < y[i])
    return res

可以说，这种看待方式比leftmost_lo/leftmost_hi方法更简单，但也不太明确。对于诸如回文集问题之类的更为复杂的场景，它也不会立即起作用（尽管也可以在其中使用它）。