70_爬楼梯
【问题描述】
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
【算法设计思想】
- 定义状态:
- 状态是指问题的一个特定阶段的状态。对于“爬楼梯”问题,状态可以定义为
dp[i]
,表示到达第i
阶楼梯的方法数。
- 状态是指问题的一个特定阶段的状态。对于“爬楼梯”问题,状态可以定义为
- 确定状态转移方程:
- 状态转移方程描述了如何从一个或多个先前的状态转移到当前状态。对于“爬楼梯”问题,状态转移方程为
dp[i] = dp[i - 1] + dp[i - 2]
,表示到达第i
阶楼梯的方法数等于到达第(i-1)
阶楼梯的方法数加上到达第(i-2)
阶楼梯的方法数。
- 状态转移方程描述了如何从一个或多个先前的状态转移到当前状态。对于“爬楼梯”问题,状态转移方程为
- 初始化:
- 初始化一些基本情况,以便开始递推计算。对于“爬楼梯”问题,初始化
dp[1] = 1
和dp[2] = 2
,表示到达第1阶楼梯有一种方法,到达第2阶楼梯有两种方法。
- 初始化一些基本情况,以便开始递推计算。对于“爬楼梯”问题,初始化
- 确定计算顺序:
- 确定状态的计算顺序,通常是从已知状态逐步推导到最终状态。对于“爬楼梯”问题,计算顺序是从
i = 3
开始,逐步计算到i = n
。
- 确定状态的计算顺序,通常是从已知状态逐步推导到最终状态。对于“爬楼梯”问题,计算顺序是从
- 返回结果:
- 最后返回所需的最终结果。对于“爬楼梯”问题,返回
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];
}