algorithm - 使用给定数量的 2 的表达式的唯一值

Question

给定 2 的个数，通过构建一个包含加法或乘法的最多给定个 2 的表达式，可以形成多少个唯一值。

例如，如果 n = 2，我们可以形成 2 个不同的值:

2 + 2 = 4
2 * 2 = 4
2     = 2

对于 n = 3，我们可以形成 4 个不同的值(2、4、6 和 8):

2 * 2 * 2 = 8
2 * 2 + 2 = 6
2 + 2 * 2 = 6
2 + 2 + 2 = 6
2 * 2     = 4
2 + 2     = 4
2         = 2

我想知道对于任何 n，不同可能值的数量。

我尝试了所有可能的组合并将它们添加到 HashMap 中，但是随着 n 的增加，组合呈指数级增长，因此蛮力无法奏效。我需要另一种计算方法或通用数学公式。

能不能用动态规划来解决，因为我看到很多子问题都是重复使用的。

Answer 1

到目前为止，其他答案都假定我们要计算不同表达式 的数量。这个答案假设我们正在寻找这些表达式可以计算出的不同值的数量。

假设您最多有一个大小表达式 n。然后我们可以将其重写为 2^e[1] + 2^e[2] + ... + 2^e[m] e[i] >= 1 和 e[1] + e[2] + ... + e[m] <= n。

让我们假设 e[1] <= e[2] <= ... <= e[m]。如果 e[i] = e[i+1] 对于某些 i，那么我们可以用单个指数 e[i] + 替换两个相等的指数1，因为 2^e[i] + 2^e[i+1] = 2 * 2^e[i] = 2^{e[i] + 1}。由于e[i] + 1 <= e[i] + e[i+1]，新的序列结果相同，仍然满足所有指数之和较小的条件小于或等于 n。

所以我们只需要计算不同指数序列的个数0 < e[1] < e[2] < ... < e[m]。很明显，每一个都代表不同的值，因为数字的二进制表示是唯一的(不同的指数恰好代表二进制表示)。

我们可以使用动态规划来计算这些序列，例如从最高到最低选择指数。

让我们将 f(n,hi) 定义为选择总和不超过 n 且最高指数为 < em><= 嗨。在每一步，我们都可以在 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