到目前为止,其他答案都假定我们想要计算不同的
表达式数量。而这个答案假设我们正在寻找这些表达式可以求值的不同
值的数量。
假设您有一个大小不超过
n的表达式。那么我们可以将其重写为
2e[1]+2e[2]+...+2e[m],其中
e[i] >= 1且
e[1]+e[2]+...+e[m] <= n。
让我们假设
e[1] <= e[2] <= ... <= e[m]。如果对于某些
i,
e[i] = e[i+1],那么我们可以用单个指数
e[i]+1替换两个相等的指数,因为
2e[i]+2e[i+1]=2*2e[i]=2e[i]+1。由于
e[i]+1 <= e[i]+e[i+1],新序列得到相同的值,并且仍满足所有指数之和小于或等于
n的条件。
因此,我们只需要计算不同指数序列的数量
0 < e[1] < e[2] < ... < e[m]。很明显,每个序列都代表一个不同的值,因为数字的二进制表示是唯一的(而不同的指数恰好代表二进制表示)。
我们可以使用动态规划来计算这些序列,例如按从高到低的顺序选择指数。
让我们定义
f(n,hi)为选择总和不超过
n且最高指数
<= hi的不同指数的数量。在每个步骤中,我们可以任意选择下一个最高指数,在
1和
min(hi,n)之间,或停止选择指数。因此,我们有以下递归关系式。
f(0, hi) = 1 for all hi >= 0
f(n, hi) = 1 + sum(e = 1 to min(hi, n), f(n - e, e - 1))
这导致了一个简单的动态规划来解决问题。答案是f(n,n) - 1
。我们需要减去一个,因为我们还计算了不选择任何指数的可能性,这会导致总和为0
。然而,根据问题陈述,这是不允许的。
以下是一些结果:
f(1,1) - 1 = 1
f(2,2) - 1 = 2
f(3,3) - 1 = 4
f(4,4) - 1 = 6
f(5,5) - 1 = 9
f(6,6) - 1 = 13
f(7,7) - 1 = 18
f(8,8) - 1 = 24
f(9,9) - 1 = 32
f(10,10) - 1 = 42
f(11,11) - 1 = 54
f(12,12) - 1 = 69
f(13,13) - 1 = 87
f(14,14) - 1 = 109