如何优化工作（但速度较慢）楼梯排列功能？

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

让dp[i][j]表示使用前i步骤可以获得j块的方法的数量

在第0行中，只有dp[0][0]将是1，其他所有内容都将是0，因为最初使用0步可以以一种方式获得0块

对于其他行，dp[i][j] = dp[i - 1][j] + dp[i - 1][j - i]因为dp[i - 1][j]是获取j块的旧方法，在使用大小为i的块之后dp[i - 1][j - i]也将有助于dp[i][j]

这使用了O(n ^ 2)空间复杂性。但您可以通过观察当前行仅依赖于前一行来将其缩减为O(n)。因此，这将空间减少到O(n)。但时间复杂度保持不变，即O(n ^ 2)

def solution(n):
    # we can reach 0 in 1 way which using no blocks
    prev = [0 for _  in range(n + 1)]
    prev[0] = 1

    # start from n - 1 block and go up to 1
    for i in range(n - 1, 0, -1):
        curr = list(prev)
        for j in range(i, n + 1):
            curr[j] = curr[j] + prev[j - i]
        prev = list(curr)
    return prev[-1]

这里prev表示dp[i-1]，curr表示dp[i]

Answer 2

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

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)

它比你的版本效率高一点，在n=105时，与你发布的版本中的13.4s相比，这需要我的计算机上的3.3s

其思想是使用越来越高的值递归地填充桶，以便满足需求

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

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)

在我的计算机上，n=105需要0.04s。但是我们也可以通过移除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/