爬楼梯动态规划（上楼梯 动态规划）

## 爬楼梯动态规划

简介

爬楼梯问题是动态规划的一个经典入门题目。它可以有多种变体，但核心思想都是利用之前计算的结果来避免重复计算，从而提高效率。本文将详细解释爬楼梯问题的基本模型及其动态规划解法，并探讨一些常见的变体。

一、 问题描述

假设你正在爬楼梯。需要

n

阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

二、 动态规划解法

1.

状态定义:

`dp[i]` 表示爬到第 `i` 阶楼梯的不同方法数。2.

状态转移方程:

考虑到达第 `i` 阶的最后一步，有两种可能：

从第 `i-1` 阶爬 1 个台阶上来。

从第 `i-2` 阶爬 2 个台阶上来。因此，爬到第 `i` 阶的方法数是爬到第 `i-1` 阶的方法数和爬到第 `i-2` 阶的方法数之和。状态转移方程为：```dp[i] = dp[i-1] + dp[i-2]```3.

初始状态:

`dp[0] = 1` (可以理解为站在地面，有一种方法到达第0阶)

`dp[1] = 1` (只有一种方法到达第1阶，即爬1个台阶)4.

计算顺序:

从小到大计算 `dp[i]`，最终结果为 `dp[n]`。

三、 代码实现 (Python)

```python def climb_stairs(n):if n <= 1:return 1dp = [0]

(n + 1)dp[0] = 1dp[1] = 1for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]# 示例 n = 5 result = climb_stairs(n) print(f"爬到{n}阶楼梯的不同方法数: {result}") ```

四、 空间优化

观察状态转移方程，可以发现 `dp[i]` 只依赖于 `dp[i-1]` 和 `dp[i-2]`。因此，不需要存储整个 `dp` 数组，只需要存储前两个状态即可。```python def climb_stairs_optimized(n):if n <= 1:return 1prev1, prev2 = 1, 1for i in range(2, n + 1):current = prev1 + prev2prev2 = prev1prev1 = currentreturn prev1# 示例 n = 5 result = climb_stairs_optimized(n) print(f"爬到{n}阶楼梯的不同方法数 (优化后): {result}") ```

五、 扩展变体

每次可以爬 1, 2, ..., m 个台阶:

状态转移方程变为 `dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-m]`。需要注意边界条件。

某些台阶不能踩:

在计算 `dp[i]` 时，需要判断第 `i` 阶是否可以踩。如果不能踩，则 `dp[i] = 0`。

有代价的爬楼梯:

除了计算方法数，还可以计算最小代价或最大代价。

总结

爬楼梯问题是动态规划的经典例题，通过分析问题，定义状态，找出状态转移方程，可以简洁高效地解决问题。理解其核心思想对于解决其他动态规划问题非常有帮助。 通过空间优化，可以进一步提高算法的效率。 同时，爬楼梯问题也有一些常见的变体，需要根据具体情况调整解法。

爬楼梯动态规划**简介**爬楼梯问题是动态规划的一个经典入门题目。它可以有多种变体，但核心思想都是利用之前计算的结果来避免重复计算，从而提高效率。本文将详细解释爬楼梯问题的基本模型及其动态规划解法，并探讨一些常见的变体。**一、 问题描述**假设你正在爬楼梯。需要 *n* 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？**二、 动态规划解法**1. **状态定义:** `dp[i]` 表示爬到第 `i` 阶楼梯的不同方法数。2. **状态转移方程:** 考虑到达第 `i` 阶的最后一步，有两种可能：* 从第 `i-1` 阶爬 1 个台阶上来。* 从第 `i-2` 阶爬 2 个台阶上来。因此，爬到第 `i` 阶的方法数是爬到第 `i-1` 阶的方法数和爬到第 `i-2` 阶的方法数之和。状态转移方程为：```dp[i] = dp[i-1] + dp[i-2]```3. **初始状态:*** `dp[0] = 1` (可以理解为站在地面，有一种方法到达第0阶)* `dp[1] = 1` (只有一种方法到达第1阶，即爬1个台阶)4. **计算顺序:** 从小到大计算 `dp[i]`，最终结果为 `dp[n]`。**三、 代码实现 (Python)**```python def climb_stairs(n):if n <= 1:return 1dp = [0] * (n + 1)dp[0] = 1dp[1] = 1for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]

示例 n = 5 result = climb_stairs(n) print(f"爬到{n}阶楼梯的不同方法数: {result}") ```**四、 空间优化**观察状态转移方程，可以发现 `dp[i]` 只依赖于 `dp[i-1]` 和 `dp[i-2]`。因此，不需要存储整个 `dp` 数组，只需要存储前两个状态即可。```python def climb_stairs_optimized(n):if n <= 1:return 1prev1, prev2 = 1, 1for i in range(2, n + 1):current = prev1 + prev2prev2 = prev1prev1 = currentreturn prev1

示例 n = 5 result = climb_stairs_optimized(n) print(f"爬到{n}阶楼梯的不同方法数 (优化后): {result}") ```**五、 扩展变体*** **每次可以爬 1, 2, ..., m 个台阶:** 状态转移方程变为 `dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-m]`。需要注意边界条件。 * **某些台阶不能踩:** 在计算 `dp[i]` 时，需要判断第 `i` 阶是否可以踩。如果不能踩，则 `dp[i] = 0`。 * **有代价的爬楼梯:** 除了计算方法数，还可以计算最小代价或最大代价。**总结**爬楼梯问题是动态规划的经典例题，通过分析问题，定义状态，找出状态转移方程，可以简洁高效地解决问题。理解其核心思想对于解决其他动态规划问题非常有帮助。 通过空间优化，可以进一步提高算法的效率。 同时，爬楼梯问题也有一些常见的变体，需要根据具体情况调整解法。