如何在基于斐波那契的爬楼梯程序中打印所有不同步数组合？

我明白你现在的需求——已经能用斐波那契的思路算出爬楼梯的总方式数，但想把每一种具体的步数组合也打印出来对吧？其实核心就是在计算斐波那契数的过程中，记录每一步的选择路径，而不是只累加计数。下面给你两种实用的实现思路和代码示例：

思路1：回溯法（直观易懂，对应递归式斐波那契） #

斐波那契的递归逻辑f(n) = f(n-1) + f(n-2)，本质就是每次有两种选择：走1步或走2步。我们可以用回溯的方式，递归探索每一种选择，当剩余阶数为0时，就把当前的路径保存下来。

代码示例（Python） #

def climb_stairs_with_paths(n):
    all_paths = []
    
    def backtrack(remaining_steps, current_path):
        # 剩余步数为0，说明找到一条有效路径
        if remaining_steps == 0:
            all_paths.append(tuple(current_path))
            return
        
        # 选择走1步（剩余步数足够时）
        if remaining_steps >= 1:
            current_path.append(1)
            backtrack(remaining_steps - 1, current_path)
            current_path.pop()  # 回溯，撤销选择
        
        # 选择走2步（剩余步数足够时）
        if remaining_steps >= 2:
            current_path.append(2)
            backtrack(remaining_steps - 2, current_path)
            current_path.pop()  # 回溯，撤销选择
    
    backtrack(n, [])
    return all_paths, len(all_paths)

# 测试n=3的情况
paths, total_count = climb_stairs_with_paths(3)
print(f"总共有{total_count}种方式：")
for path in paths:
    print(path)

运行后会输出：

总共有3种方式：
(1, 1, 1)
(1, 2)
(2, 1)

思路2：动态规划（迭代式，完美匹配斐波那契递推逻辑） #

如果你原来的斐波那契实现是用动态规划迭代的，那可以直接扩展dp数组，让它不仅存储计数，还存储对应阶数的所有路径：

• dp[i] 表示爬i阶楼梯的所有步数组合
• 递推逻辑：dp[i] = 所有dp[i-1]的路径末尾加1 + 所有dp[i-2]的路径末尾加2

代码示例（Python） #

def climb_stairs_dp_paths(n):
    # 初始化dp数组，每个元素是路径列表
    dp = [[] for _ in range(n + 1)]
    dp[0] = [()]  # 0阶楼梯的基础路径（空路径）
    
    if n >= 1:
        dp[1] = [(1,)]  # 1阶楼梯只有一种路径
    
    for i in range(2, n + 1):
        # 把dp[i-1]的所有路径末尾加1，加入dp[i]
        for path in dp[i-1]:
            dp[i].append(path + (1,))
        # 把dp[i-2]的所有路径末尾加2，加入dp[i]
        for path in dp[i-2]:
            dp[i].append(path + (2,))
    
    return dp[n], len(dp[n])

# 测试
paths, total_count = climb_stairs_dp_paths(3)
print(f"总共有{total_count}种方式：")
for path in paths:
    print(path)

两种方式对比 #

• 回溯法：逻辑直观，容易理解，但递归深度受限于n的大小（n太大可能栈溢出）。
• 动态规划：迭代实现更稳定，完全贴合斐波那契的递推逻辑，适合和你原来的计数程序整合，而且路径存储更有序。

内容的提问来源于stack exchange，提问作者justoneday