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

Question

我的编程作业在给定的限制条件下无法解决。

条件：

您有 N 块积木。

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

每个楼梯都应该使用所有给定的砖块建造。
不允许两个高度相同的台阶。
楼梯应该至少有 2 个台阶。
最多提供 250 个积木。

示例：

给定 3 块砖，您可以建造 1 个楼梯：

step 1 - height 1
step 2 - height 2

给定 4 块砖，你也可以建造 1 个楼梯：

step 1 - height 1
step 2 - height 3

给定 5 块砖，你可以建造 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类被限制等等。

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

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

tree structure

我尝试了几种方法：

自下而上（从最低台阶到最高台阶）和自上而下（从最高台阶到最低台阶）建造楼梯
使用深度优先和广度优先搜索。
使用递归或迭代。

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

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");
 }
}

对不起，因为我大部分时间都是晚上学习，白天工作，所以很乱。 python2也可以用，不过我不专业

Answer 1

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

使用上面link中的生成函数的一个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，这将等于 product(1+x^k for k=1..n).

（实际上，此解决方案包括步长为 N 的 "stair" - 因此您必须减去 1 才能得到排除这种特殊情况的结果）。

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

How to increase the speed of calculation the number of specific leaves in tree

java

algorithm

tree

graph-theory