问题是，给定许多块，有多少种方法可以使用有限数量的块来建造楼梯，其中任何两个相邻台阶之间总是有任何倾斜。
这意味着从 100 到 1 步的两步楼梯是有效的。当然，更多的块意味着你可以有更多的步骤。
我编写了一个函数来实现这一点，尽管当它到达更多的块时非常慢，我不确定如何改进它的运行时。
如果你想快速分解我的逻辑，从逻辑上讲，通过递归地将最高步扩展到两个步骤的所有可能排列(这仍然会使第二步高于前一步的第二步(，最终你会得到所有可能的步骤排列。
也许有一种更数学的方法可以做到这一点，但我是从编程 pov 开始的。欢迎听到任何不同的建议，如果我的方法太慢了！
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
这是一种替代的递归/回溯方法：
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)
这需要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/
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]