假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2 输出: 2 解释: 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2:
输入: 3 输出: 3 解释: 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/climbing-stairs
思路:
因为只用返回的是有几种解决的办法,不用返回具体的解决办法是什么
所以问题就变的简单了起来
第一阶有一种方法,第二阶有两种方法,第三阶就有第一阶方法数加上第二阶方法数的方法,第四阶的方法等于(第一阶 + 第二阶 + 第三阶)
所以就是一个斐波那契数列
class Solution { public int climbStairs(int n) { int [] level = new int [n]; int before = 1; int after = 2; for (int i = 0; i < n; i++) { if (i == 0){ level[i] = before; }else if (i == 1){ level[i] = after; }else { level[i] = level[i - 1] + level[i - 2]; } } return level[n - 1]; } }
Solution2
public int climbStairs(int n) { if (n <= 2) { return n; } int pre2 = 1, pre1 = 2; for (int i = 2; i < n; i++) { int cur = pre1 + pre2; pre2 = pre1; pre1 = cur; } return pre1; }