# 70. Climbing Stairs 爬楼梯

@TOC

[LeetCode]

Total Accepted: 106510 Total Submissions: 290041 Difficulty: Easy

## # 题目大意

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

``````Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
``````

Example 2:

``````Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
``````

## # 解题方法

### # 递归

``````1 --> 1
2 --> 2
3 --> 3
4 --> 5
……
``````

``````public class Solution {

public int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
return climbStairs(n-1)+climbStairs(n-2);
}
}
``````

### # 记忆化搜索

``````class Solution(object):
def __init__(self):
self.memo = dict()
self.memo[0] = 1
self.memo[1] = 1

def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n in self.memo:
return self.memo[n]
steps = self.climbStairs(n - 1) + self.climbStairs(n - 2)
self.memo[n] = steps
return steps
``````

### # 动态规划

``````public class Solution {

public int climbStairs(int n) {
int[] counts=new int[n+1];
counts[0]=1;
counts[1]=1;
for(int i=2;i<=n;i++){
counts[i]=counts[i-1]+counts[i-2];
}
return counts[n];
}
}
``````

AC:0ms

DP的Python解法如下：

``````class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[-1]
``````

### # 空间压缩DP

Java解法如下：

``````public class Solution {

public int climbStairs(int n) {
int[] counts=new int[3];
counts[0]=1;
counts[1]=1;
for(int i=2;i<=n;i++){
counts[i%3]=counts[(i-1)%3]+counts[(i-2)%3];
}
return counts[n%3];
}
}
``````

AC:0ms

Python解法如下：

``````class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
first, second = 1, 2
for i in range(3, n + 1):
third = first + second
first = second
second = third
return second
``````

## # 日期

2016/5/1 16:19:44 2018 年 11 月 19 日 —— 周一又开始了