### 使用递归和动态规划解决10阶楼梯的走法总数 #### 方法一：递归实现 通过定义一个递归函数 `ways` 来解决问题。该函数的核心逻辑是基于以下关系式： \[ \text{ways}(n) = \text{ways}(n-1) + \text{ways}(n-2) \] 其中，当 \( n = 0 \) 或 \( n = 1 \) 时，返回值为 1。 以下是具体的 Python 实现代码： ```python def ways(n): if n == 0 or n == 1: # 当台阶数为0或1时，只有一种方式 return 1 return ways(n - 1) + ways(n - 2) # 递归调用 # 测试程序 n = 10 result = ways(n) print(f"Result={result}") ``` 上述代码的时间复杂度较高，主要由于重复计算子问题的结果[^3]。 --- #### 方法二：动态规划实现 为了优化时间性能并减少冗余计算，可以采用动态规划的方式求解。核心思想是利用状态转移方程： \[ dp[i] = dp[i-1] + dp[i-2] \] 具体实现如下： ```python def climb_stairs(n): if n <= 0: return 0 elif n == 1: return 1 elif n == 2: return 2 dp = [0] * (n + 1) # 初始化dp数组 dp[1], dp[2] = 1, 2 # 设置初始条件 for i in range(3, n + 1): # 动态规划填充过程 dp[i] = dp[i - 1] + dp[i - 2] return dp[n] # 返回最终结果 # 测试程序 n = 10 result = climb_stairs(n) print(f"Result={result}") ``` 这种方法的时间复杂度为 \(O(n)\)，空间复杂度也为 \(O(n)\)[^2]。 --- #### 方法三：进一步优化的空间复杂度 可以通过仅保留两个变量来代替整个 DP 数组，从而将空间复杂度降低到 \(O(1)\): ```python def optimized_climb_stairs(n): if n <= 0: return 0 elif n == 1: return 1 elif n == 2: return 2 prev_1, prev_2 = 1, 2 # 定义前两步的状态 current = 0 for _ in range(3, n + 1): # 更新当前状态 current = prev_1 + prev_2 prev_1, prev_2 = prev_2, current return prev_2 # 返回最后一步的结果 # 测试程序 n = 10 result = optimized_climb_stairs(n) print(f"Result={result}") ``` 这种优化版本不仅保持了 \(O(n)\) 的时间复杂度，还将空间复杂度降到了最低水平[^2]。 --- ### 结果分析 对于输入 \(n = 10\) 阶梯的情况，三种方法均能得出相同的结果： \[ Result=89 \] 这表明无论使用哪种方法，都可以正确计算出总共有 89 种不同的走法[^1]。 ---