如何优化楼梯问题的 python 代码以使用更大的值？

Question

我必须为楼梯问题创建一个程序，我必须用 n 块积木设计楼梯。复杂的是每一步的砖块数量必须是唯一的，并且比上一步要少。例如，使用 6 块砖，我可以制作阶梯高度为 (5,1) , (4,2) and (3,2,1) 而不是 (3,3) or (1,2,3) or (2,4) 或任何其他排列的楼梯。

我已经设计了代码，但问题是它运行没问题，直到 n 接近 100 或 120，但如果输入大于这些值，它就会冻结。我是 Python 编程和随时随地学习概念的初学者。

我试过记忆，但没有用。我需要知道是否还有其他方法可以使我的代码更优化为运行而不是 n 为 200-250?

    import cProfile

    def solution(n):

        memory = {0: [], 1: [1], 2: [2]}

        def rec(max_val, i):

            t = []
            r = []

            for j in range(1,i):

                y = i - j

                if y < max_val:

                    if y > j:
                        t = [y, j]
                        r.append(t)

                        if n / 2 >= j >= 3 and j in memory:
                            mem = memory[j]
                            [r.append([y, item]) for item in mem]

                    else:
                        if y >= 3 and n / 2 >= j >= 3 and j in memory:
                            mem = memory[j]
                            for item in mem:
                                if y > item[0]:
                                    r.append([y, item])
                        else:
                            v = rec(y, j)
                            if v:
                                for item in v:
                                    t = [y, item]
                                    r.append(t)

            if r:
                if i in memory:
                    if len(memory[i]) < len(r):
                        memory[i] = r
                else:
                    memory[i] = r
            return r

        def main_func(n):

            stair = []
            max_val = 201
            total = 0
            for i in range (1,n):

                x = n - i

                if x > i:
                    s = [x, i]
                    total += 1

                    if i >= 3:
                        u = rec(max_val, i)
                        total += len(u)

                elif x == i and i >= 3:
                        u = rec(max_val, i)
                        total += len(u)

                elif x < i and i >= 3:
                        u = rec(x, i)
                        total += len(u)

            return total

        stairs = main_func(n)
        return (stairs)

    print(solution(100))

Answer 1

您可以从楼梯底部的角度递归地解决问题。该策略是将每个基本尺寸的下一步级别的模式计数相加。

例如，对于 6 块积木，第一次调用将通过基本尺寸 n = 5、4、3、2 并进行递归调用以了解使用剩余积木的下一步级别可能有多少种组合并且最大基数为 n-1。下一级计数的总和将构成可能的楼梯模式的总数。

在楼梯的顶部，您至少需要 3 块积木才能增加一层以上，这样当剩余的积木少于 3 块时，您可以停止递归，计数为 1。这将汇总递归调用以形成更大的总数，并在原始调用完成后产生正确的答案。

为了优化这个过程，您可以使用记忆，也可以使用每次递归时提供的基本大小来缩短计算。

对于给定的底座，可以使用的最大积木数量将是从 1 到该底座的数字总和。这可以使用高斯公式计算：base*(base+1)/2。如果你的砖块数量超过了基地的最大砖块数量，那么你可以停止递归并且 return 计数为零（因为你有太多剩余的砖块并且将无法在之前的过程中装满它们关卡的基础）

另一种优化计算的方法是以降序循环遍历基本大小。这将允许您在下一级别的计数为零时立即停止循环，这意味着该基本尺寸（或任何更小的基本尺寸）剩余的砖块太多

这是一个示例（使用 lru_cache 进行记忆）：

from functools import lru_cache
@lru_cache(None)
def stairCount(N,base=None):
    base = min(base or N-1,N)
    if N > base*(base+1)//2: return 0
    if N < 3: return 1
    count = 0
    while True:
        nextLevels = stairCount(N-base,base-1)
        if nextLevels == 0: break
        count += nextLevels
        base   = base - 1
    return count

通过这些优化，该函数将在不到一秒内响应最多 600 个砖块（取决于您计算机的速度）。

有了Python的列表理解，你可以把这个函数写得更简洁（虽然它会失去递减基序优化≈10%）：

@lru_cache(None)
def stairCount(N,base=None):
    base = min(base or N-1,N)
    if N > base*(base+1)//2: return 0
    if N < 3: return 1
    return sum(stairCount(N-b,b-1) for b in range(2,base+1))

编辑这是一个带有 "manual" 记忆的版本（即不使用 functools）：

def stairCount(N,base=None,memo=dict()):
    memoKey = (N,base)
    if memoKey in memo: return memo[memoKey]
    base = min(base or N-1,N)
    if N > base*(base+1)//2: return 0
    if N < 3: return 1
    count = 0
    while True:
        nextLevels = stairCount(N-base,base-1,memo)
        if nextLevels == 0: break
        count += nextLevels
        base   = base - 1
    memo[memoKey] = count
    return count

如何优化楼梯问题的 python 代码以使用更大的值？

how to optimize the python code of staircase problem to work with larger values?

python

optimization

out-of-memory