做博物馆网站最重要百度普通收录

https://leetcode.cn/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-100-liked

70. 爬楼梯
已解答
简单
相关标签
相关企业
提示
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路分析：
状态定义：

设 dp[i] 表示爬到第 i 阶楼梯的方法总数。
状态转移方程：

对于每个阶梯 i，你可以从第 i-1 阶跳 1 阶，或者从第 i-2 阶跳 2 阶。因此，dp[i] = dp[i-1] + dp[i-2]。这意味着到达第 i 阶的总方法数等于到达第 i-1 阶的方法数和到达第 i-2 阶的方法数之和。

官方解法里对前面三层的算法里我感觉不太好懂，在评论区找了个好懂的解法

public int climbStairs(int n) {// 爬一楼int p = 1;// 爬二楼int q = 2;if(n == 1){return p;}else if(n == 2){return q;}else{// 从第三楼开始，只有两种上楼方式，从前一层再爬一楼和从前二层再爬两楼。// 可以推出 f(n) = f(n -1) + f(n -2)// 直接递归会超时，所以用的for循环求结果int r = 0;for(int i = 3; i <= n; i++){r = q + p;p = q;q = r;}return r;}}