如何优化工作（但很慢）的楼梯排列函数？

Question

问题是，给定许多块，有多少种方法可以使用有限数量的块来建造楼梯，其中任何两个相邻台阶之间总是有任何倾斜。

这意味着从 100 到 1 步的两步楼梯是有效的。当然，更多的块意味着你可以有更多的步骤。

我编写了一个函数来实现这一点，尽管在处理大量块时速度非常慢，而且我不确定如何改进其运行时。

如果你想快速分解我的逻辑，从逻辑上讲，通过递归地将最高步骤扩展为两个步骤的所有可能排列（这仍然会将第二步放在前一个第二步之上），最终你会得到所有可能的步骤排列.

也许有一种更数学的方法可以做到这一点，但我是从编程观点来看的。如果我的方法太慢，欢迎听到任何不同的建议！

def solution(n):
    cases = 0
    q = [[x, n - x] for x in range(n) if x > n - x and n - x > 0]
    
    while q:
        curr = q.pop(0)
        cases += 1
        q += [[x, curr[0] - x, *curr[1:]] for x in range(curr[1], curr[0] - curr[1]) if x > curr[0] - x > curr[1]]
        
    return cases

输出，以显示它的工作原理

>>> solution(15)
[8, 7]
[9, 6]
[10, 5]
[11, 4]
[12, 3]
[13, 2]
[14, 1]
[6, 5, 4]
[7, 5, 3]
[8, 4, 3]
[7, 6, 2]
[8, 5, 2]
[9, 4, 2]
[10, 3, 2]
[8, 6, 1]
[9, 5, 1]
[10, 4, 1]
[11, 3, 1]
[12, 2, 1]
[6, 4, 3, 2]
[6, 5, 3, 1]
[7, 4, 3, 1]
[7, 5, 2, 1]
[8, 4, 2, 1]
[9, 3, 2, 1]
[5, 4, 3, 2, 1]
26

Answer 1

这是另一种递归/回溯方法：

def solve_recursive(n):
    solutions = []
    def f(sol, i, n):
        if n == 0 and len(sol) >= 2:
            solutions.append(sol)

        for j in range(i+1, n+1):
            sol.append(j)
            f(sol, j, n-j)
            sol.pop()
    f([], 0, n)
    return len(solutions)

3.3s与13.4s您发布的版本相比，它比您的版本效率更高，在 n=105 时，这需要在我的计算机上运行。

这个想法是使用越来越高的值递归地填充桶，以满足要求。

如果我们只对计数感兴趣，而不对路径感兴趣，我们可以通过省略路径簿记来加快速度：

from functools import lru_cache

def solution_faster(n):
    @lru_cache(maxsize=None)
    def f(i, cnt, n):
        if n == 0 and cnt >= 2:
            return 1
        ans = 0        
        for j in range(i+1, n+1):
            ans += f(j, cnt+1, n-j)
        return ans

    return f(0, 0, n)

这0.04s在我的计算机上需要n=105。但是我们也可以通过删除 来做得更好cnt！

def solution_even_faster(n):
    @lru_cache(maxsize=None)
    def f(i, n):
        if n == 0:
            return 1
        ans = 0        
        for j in range(i+1, n+1):
            ans += f(j, n-j)
        return ans

    ans = 0
    for j in range(1, n//2 + 1):
        ans += f(j, n-j)
    return ans

现在我们有了O(N^3)（伪多项式）时间复杂度。这需要0.008s我的电脑。

O(N^2)解决方案也可以使用动态规划方法。我建议查看此参考：https : //www.geeksforgeeks.org/count-of-subsets-with-sum-equal-to-x/