leetcode 70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
题解:
1. n 阶楼梯
2.每次可以爬1或2个台阶
3.问有多少种不同的方法爬到楼顶
示例 1:
输入:2
输出:2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入:3
输出:3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
解题思路:
仔细分析n=0,1,2,3的情况下,实际上就是在求斐波那契数列
C/C++题解:
class Solution {
public:
int climbStairs(int n) {
int f1 = 1,f2 = 2;//斐波那契数列初始值
if (n == 1) return f1;
if(n == 2) return f2;
for(int i =3;i<=n;i++){//求等于n时的斐波那契数值
int tmp = f1 + f2;
f1 = f2;//f2的值赋给f1
f2 = tmp;}//新值赋给f2
return f2;}};//这样最后返回f2的值
Debug结果:
Java题解:
class Solution {
public int climbStairs(int n) {
int f1 = 1,f2 = 2;//斐波那契数列初始值
if (n == 1) return f1;
if(n == 2) return f2;
for(int i =3;i<=n;i++){//求等于n时的斐波那契数值
int tmp = f1 + f2;
f1 = f2;//f2的值赋给f1
f2 = tmp;}//新值赋给f2
return f2;}}//这样最后返回f2的值
Debug结果:
Python题解:
class Solution(object):
def climbStairs(self, n):
""":type n: int:rtype: int"""
f1 ,f2 = 1 ,2 #斐波那契数列初始值
if (n == 1): return f1
if(n == 2): return f2
for i in range(3, n+1): #求等于n时的斐波那契数值
f1, f2 = f2, f1 + f2;#f2的值赋给f1,新值赋给f2
return f2 #这样最后返回f2的值
Debug结果:
更多题解可前往公众号免费获取