# 70. Climbing Stairs

You are climbing a staircase. It takes `n` steps to reach the top.

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

Example 1:

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

Example 2:

``````Input: n = 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
``````

Constraints:

• `1 <= n <= 45`

C++ 解法一：

``````class Solution {
public:
int climbStairs(int n) {
if (n <= 1) return 1;
vector<int> dp(n);
dp[0] = 1; dp[1] = 2;
for (int i = 2; i < n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp.back();
}
};
``````

Java 解法一：

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

C++ 解法二：

``````class Solution {
public:
int climbStairs(int n) {
long a = 1, b = 1;
while (n--) {
b += a;
a = b - a;
}
return a;
}
};
``````

Java 解法二：

``````public class Solution {
public int climbStairs(int n) {
long a = 1, b = 1;
while (n-- > 0) {
b += a;
a = b - a;
}
return a;
}
}
``````

C++ 解法三：

``````class Solution {
public:
int climbStairs(int n) {
vector<int> memo(n + 1);
return helper(n, memo);
}
int helper(int n, vector<int>& memo) {
if (n <= 1) return 1;
if (memo[n] > 0) return memo[n];
return memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
}
};
``````

Java 解法三：

``````public class Solution {
public int climbStairs(int n) {
int[] memo = new int[n + 1];
return helper(n, memo);
}
public int helper(int n, int[] memo) {
if (n <= 1) return 1;
if (memo[n] > 0) return memo[n];
return memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
}
}
``````

C++ 解法四：

``````class Solution {
public:
int climbStairs(int n) {
if(n <= 1) return 1;
return climbStairs(n / 2) * climbStairs(n - n / 2) + climbStairs(n / 2 - 1) * climbStairs(n - n / 2 - 1);
}
};
``````

Java 解法四：

``````public class Solution {
public int climbStairs(int n) {
if(n <= 1) return 1;
return climbStairs(n / 2) * climbStairs(n - n / 2) + climbStairs(n / 2 - 1) * climbStairs(n - n / 2 - 1);
}
}
``````

Fn = (1 / sqrt(5))(((1 + sqrt(5)) / 2) ^ n - ((1 - sqrt(5)) / 2) ^ n)

C++ 解法五：

``````class Solution {
public:
int climbStairs(int n) {
double root5 = sqrt(5);
return (1 / root5) * (pow((1 + root5) / 2, n + 1) - pow((1 - root5) / 2, n + 1));
}
};
``````

Java 解法五：

``````public class Solution {
public int climbStairs(int n) {
double root5 = Math.sqrt(5);
double res =  (1 / root5) * (Math.pow((1 + root5) / 2, n + 1) - Math.pow((1 - root5) / 2, n + 1));
return (int)res;
}
}
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/70

Min Cost Climbing Stairs

Fibonacci Number

N-th Tribonacci Number

Minimum Rounds to Complete All Tasks

Count Number of Ways to Place Houses

Number of Ways to Reach a Position After Exactly k Steps

Count Ways To Build Good Strings

Frog Jump II

https://leetcode.com/problems/climbing-stairs/discuss/25345/Easy-solutions-for-suggestions.

https://leetcode.com/problems/climbing-stairs/discuss/25296/3-4-short-lines-in-every-language

https://leetcode.com/problems/climbing-stairs/discuss/25608/My-divide-and-conquer-way-to-solve-this-problem(Java)

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation