java - 如何提高计算树中特定叶子数量的速度

Question

我有一个编程任务，在给定的约束条件下我无法解决。

条件:

你有 N block 积木。

计算您可以使用这些积木搭建多少个楼梯，条件如下:

1. 每个楼梯都应该使用所有给定的砖 block build 。
2. 不允许两个高度相同的台阶。
3. 楼梯应该至少有 2 个台阶。
4. 最多可提供 250 block 积木。

例子:

给定 3 block 积木，你可以搭建 1 个楼梯:

step 1 - height 1
step 2 - height 2

给定 4 block 积木，您还可以搭建 1 个楼梯:

step 1 - height 1
step 2 - height 3

给定 5 block 积木，你可以 build 2 个楼梯:

step 1 - height 2            step 1 - height 1
step 2 - height 3            step 2 - height 4

解决方案应该像下面这样实现(我使用的是 Java):

class Solution {
  public static int count(int numberOfBricks) {
    // code
  }
}

自动分级机有几个技术限制，例如。不允许线程，很多Java类被限制等等。

我尝试使用树结构来解决这个问题，其中每个节点都保存有关剩余砖 block 数量和当前台阶高度的信息，并且每条边代表具有允许高度的台阶的构建。

例如，以下结构表示阶梯高度为 (1,2,4) (1,6) (2,5) (3,4) 的楼梯

tree structure

我尝试了几种方法:

1. 自下而上(从最低台阶到最高台阶)和自上而下(从最高台阶到最低台阶) build 楼梯
2. 使用深度优先和广度优先搜索。
3. 使用递归或迭代。

因此，我有几个通过单元测试的可行解决方案(正确解决了所有示例问题)。不幸的是，我无法获得最高分，因为自动评分器告诉我我的解决方案落后于允许的时间限制，因此存在一些更优化的方法。我想关键是通过计算当前节点底部可能的楼梯数量来限制沿分支的遍历。不幸的是，我没有足够的知识来进行以下改进，将不胜感激任何帮助。这是我的解决方案之一:

import org.testng.Assert;

public class Task0302 {

static int numberOfStairCases = 0;

public static int answer(int n) {   
  numberOfStairCases = 0;
  run(n, n - 1);
  return numberOfStairCases;
}

static void run(final int hasBricks, final int maximalAllowedHeight) {
  if (hasBricks > bricksAllowed(maximalAllowedHeight))
    return;
  if (hasBricks == bricksAllowed(maximalAllowedHeight)) {
    numberOfStairCases++;
    return;
}

int currentStepHeight = Math.min(hasBricks, maximalAllowedHeight);
final int minHeight = minPossibleHeight(hasBricks);
 do {    
   run(hasBricks - currentStepHeight, currentStepHeight - 1);
   currentStepHeight--;
 } while (currentStepHeight >= minHeight);
}

static int minPossibleHeight(int havingBricks) {
  return (int) ((Math.sqrt(8 * havingBricks + 1) - 1) / 2);
}

static int bricksAllowed(int currentHeight) {
  return (currentHeight + 1) * currentHeight / 2;
}

public static void main(String[] args) {
 Assert.assertEquals(answer(3), 1);
 Assert.assertEquals(answer(4), 1);
 Assert.assertEquals(answer(5), 2);
 Assert.assertEquals(answer(200), 487067745);
 System.out.println("Passed");
 }
}

对不起，这里很乱，因为我主要是晚上学习，白天工作。 python 2也可以，不过我不是专业的。

Answer 1

你的问题等同于计算求和到 N 的唯一正整数的方式数，忽略顺序。这里有一个引用:http://mathworld.wolfram.com/PartitionFunctionQ.html

一个O(n^2)算法使用上面链接中的生成函数计算多项式乘积:product((1+x^k) for k = 1..N)，然后看系数的 x^N。

这听起来很难，但它的代码相对简单(这里是伪代码):

A = [1, 0, 0, ..., 0] -- an array of size N+1
for k = 1 to N
    for i = N to k step -1
        A[i] += A[i - k]
return A[N]

您可以将其视为动态规划解决方案。在 k 循环的 n 步之后，每个 A[i] 将使用整数 1 到 n 存储对 i 求和的不同方式的数量。或者等价地，在 k 循环的 n 步之后，你可以认为数组 A 表示多项式 A[0] + A[1]x + A[2]x^2 + ... + A[N]x^ N，等于乘积(1+x^k for k=1..n)。

(实际上，此解决方案包括一步大小为 N 的“楼梯”——因此您必须减去 1 才能得到不包括这种特殊情况的结果)。