4

我在准备面试时发现了以下问题：

3可以写成1+1+1、1+2、2+1；4可以写成1+1+1+1、1+1+2、2+2、1+2+1、2+1+1、3+1、1+3；给定一个整数，存在多少个可能的表达式？（1+2和2+1不同）

因此，编写一个蛮力算法来计算它并获得所有执行它的数字集的集合是相当简单的：

private static Set<List<Integer>> getIntegersSum(int num) {
  Set<List<Integer>> returnSet = new HashSet<List<Integer>>();

  if (num == 0) {
   returnSet.add(new LinkedList<Integer>());
   return returnSet;
  }

  for (int i = 1; i <= num; i++) {
    Set<List<Integer>> listNMinI = getIntegersSum(num - i);
    for (List<Integer> l : listNMinI) {
      l.add(0, i);
      returnSet.add(l);
    }
  }

  return returnSet;
}

现在我相信描述这个算法复杂性的递归关系是：

T(0) = \Theta (1)
T(n) = O(n) + \Sum_{i=0}^{n-1} T(i)

我不太确定如何从这种递归关系中得出很大的复杂性。我还想知道这个问题是否有一个封闭形式的解决方案（每个数字我们会有多少这样的组合）。

我也不确定如果我们通过缓存每个调用的结果来记忆这个算法（类似于如何加速斐波那契），那么复杂性会是多少。

4

1 回答 1

2

有 2 n - 1 - 1 个这样的表达式。

有很多方法可以解决这个问题。

我使用这个问题的结果：

有 n 颗糖果。有多少种方法可以将所有 n 颗糖果分给 k 个人（可以给 0 颗糖果）？

顺序很重要，因为这些部分是分给不同的人的。解是 (n + k - 1)C(k - 1)。我们将 k - 1 个分隔符添加到混合中（这使得总和为 n + k - 1），并且我们尝试找到插入分隔符以将糖果分成 k 个部分的方法的数量。考虑在一行中放置 n + k - 1 个盒子来放置糖果和分隔符，我们想要找到多种方法来为分隔符选择 k - 1 个插槽，从而将盒子分成 k 个部分。

回到这个问题，我们需要回答这个子问题：

有多少种方法可以将 n 表示为 k 个正数之和？

我们可以重用上面糖果分裂问题的结果，但是我们需要保留 k 以防止项为 0。所以结果将是 ((n - k) + k - 1)C(k - 1)，即简化为 (n - 1)C(k - 1)。（(n - k) 是由于我们为 k 项中的每一项都放了 k 项）。

所以最终结果将是 Sum [i = 2..n] (n - 1)C(i - 1)，因为表达式包含至少 2 个项，最多 n 个项。我们知道 Sum [i = 1..n] (n - 1)C(i - 1) = 2 n - 1，所以 Sum [i = 2..n] (n - 1)C(i - 1) = 2 n - 1 - 1。

@MarkDickinson 在评论中解释了解决此问题的另一种方法。推理更直接。

在每对糖果之间，要么有分隔符，要么没有。这立即提供了2^(n-1)可能性。无论出于何种原因，OP 都排除了我们只有 1 部分的单一情况，因此减去 1 得到2^(n-1) - 1.

使论据更加扎实。由于该问题只允许正项，我们只能在糖果之间插入 1 个分隔符，我们只能在糖果之间插入它们，而不是 2 端。因此，有 (n - 1) 个位置可以出现分隔符。

于 2012-12-22T17:29:02.030 回答