70_爬楼梯

70_爬楼梯

【问题描述】

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

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

【算法设计思想】

1. 定义状态：
   • 状态是指问题的一个特定阶段的状态。对于“爬楼梯”问题，状态可以定义为 dp[i]，表示到达第 i 阶楼梯的方法数。
2. 确定状态转移方程：
   • 状态转移方程描述了如何从一个或多个先前的状态转移到当前状态。对于“爬楼梯”问题，状态转移方程为 dp[i] = dp[i - 1] + dp[i - 2]，表示到达第 i 阶楼梯的方法数等于到达第 (i-1) 阶楼梯的方法数加上到达第 (i-2) 阶楼梯的方法数。
3. 初始化：
   • 初始化一些基本情况，以便开始递推计算。对于“爬楼梯”问题，初始化 dp[1] = 1 和 dp[2] = 2，表示到达第1阶楼梯有一种方法，到达第2阶楼梯有两种方法。
4. 确定计算顺序：
   • 确定状态的计算顺序，通常是从已知状态逐步推导到最终状态。对于“爬楼梯”问题，计算顺序是从 i = 3 开始，逐步计算到 i = n。
5. 返回结果：
   • 最后返回所需的最终结果。对于“爬楼梯”问题，返回 dp[n]，即到达第 n 阶楼梯的方法数。

【算法描述】

C++：

class Solution {
public:int climbStairs(int n) {// 如果楼梯只有1阶，那么只有一种爬法，直接返回1if (n == 1) return 1;// 如果楼梯有2阶，那么有两种爬法：一次爬1阶两次，或者一次爬2阶，直接返回2if (n == 2) return 2;// 创建一个大小为n+1的数组dp，用于存储从第0阶到第n阶的爬法数量int dp[n + 1];// 初始化dp数组的前几个值dp[0] = 0; // 从第0阶开始，没有爬法dp[1] = 1; // 从第1阶开始，只有一种爬法dp[2] = 2; // 从第2阶开始，有两种爬法// 从第3阶开始，使用动态规划计算每一阶的爬法数量for (int i = 3; i <= n; i++) {// 到达第i阶的爬法数量等于到达第(i-1)阶的爬法数量加上到达第(i-2)阶的爬法数量dp[i] = dp[i - 1] + dp[i - 2];}// 返回到达第n阶的爬法数量return dp[n];}
};

---

Java：

class Solution {public int climbStairs(int n) {// 如果楼梯只有1阶，那么只有一种爬法，直接返回1if (n == 1) {return 1;}// 如果楼梯有2阶，那么有两种爬法：一次爬1阶两次，或者一次爬2阶，直接返回2if (n == 2) {return 2;}// 创建一个大小为n+1的数组dp，用于存储从第0阶到第n阶的爬法数量int[] dp = new int[n + 1];// 初始化dp数组的前几个值dp[1] = 1; // 从第1阶开始，只有一种爬法dp[2] = 2; // 从第2阶开始，有两种爬法// 从第3阶开始，使用动态规划计算每一阶的爬法数量for (int i = 3; i <= n; i++) {// 到达第i阶的爬法数量等于到达第(i-1)阶的爬法数量加上到达第(i-2)阶的爬法数量dp[i] = dp[i - 1] + dp[i - 2];}// 返回到达第n阶的爬法数量return dp[n];}
}

---

Python：

class Solution:def climbStairs(self, n: int) -> int:# 创建一个大小为n+1的列表dp，用于存储从第0阶到第n阶的爬法数量dp = [0] * (n + 1)# 如果楼梯只有0阶，根据题目假设，返回0（实际上这种情况可能不需要处理）if n == 0:return 0# 如果楼梯只有1阶，那么只有一种爬法，直接返回1if n == 1:return 1# 如果楼梯有2阶，那么有两种爬法：一次爬1阶两次，或者一次爬2阶，直接返回2if n == 2:return 2# 初始化dp数组的前几个值dp[0] = 0  # 从第0阶开始，没有爬法dp[1] = 1  # 从第1阶开始，只有一种爬法dp[2] = 2  # 从第2阶开始，有两种爬法# 从第3阶开始，使用动态规划计算每一阶的爬法数量for i in range(3, n + 1):# 到达第i阶的爬法数量等于到达第(i-1)阶的爬法数量加上到达第(i-2)阶的爬法数量dp[i] = dp[i - 1] + dp[i - 2]# 返回到达第n阶的爬法数量return dp[n]

---

C：

int climbStairs(int n) {// 如果楼梯只有1阶，那么只有一种爬法，直接返回1if (n == 1) return 1;// 如果楼梯有2阶，那么有两种爬法：一次爬1阶两次，或者一次爬2阶，直接返回2if (n == 2) return 2;// 创建一个大小为n+1的数组dp，用于存储从第0阶到第n阶的爬法数量int dp[n + 1];// 初始化dp数组的前几个值dp[0] = 0; // 从第0阶开始，没有爬法dp[1] = 1; // 从第1阶开始，只有一种爬法dp[2] = 2; // 从第2阶开始，有两种爬法// 从第3阶开始，使用动态规划计算每一阶的爬法数量for (int i = 3; i <= n; i++) {// 到达第i阶的爬法数量等于到达第(i-1)阶的爬法数量加上到达第(i-2)阶的爬法数量dp[i] = dp[i - 1] + dp[i - 2];}// 返回到达第n阶的爬法数量return dp[n];
}