如何优化工作（但缓慢）的楼梯排列功能？

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

这是另一种 recursive/backtracking 方法：

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 时，这在我的计算机上需要 3.3s，而在您发布的版本中需要 13.4s。

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

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

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/

Answer 2

让 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) space 复杂度。但是您可以通过观察当前行仅取决于前一行来将其减少到 O(n)。所以这将 space 减少到 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]

如何优化工作（但缓慢）的楼梯排列功能？

How to optimize working (but slow) stair permutation function?

python

permutation

python-3.x