# Question

Formatted question description: https://leetcode.ca/all/70.html

70	Climbing Stairs

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

@tag-dp


# Algorithm

You can only climb 1 or 2 steps at a time, so the method to climb to the nth layer is either from the n-1 layer one step up, or from the n-2 layer 2 steps up, so the recursive formula is very easy We get: dp[n] = dp[n-1] + dp[n-2].

# Code

Java

• 
public class Climbing_Stairs {

public class Solution {
public int climbStairs(int n) {

if (n <= 0) {
return 0;
}

// dp[i], ways to i
int[] dp = new int[n + 1];

dp = 1; // to make dp correct when adding up
dp = 1;

for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}

return dp[n];
}
}

/*
Time complexity : O(2^n)
Size of recursion tree will be 2^n
*/
class Solution_recursive_cache {
public int climbStairs(int n) {
if (n <= 0) {
return 0;
}

int[] cache = new int[n + 1];
return dfs(n, 0, cache);
}

private int dfs(int n, int current, int[] cache) {

if (current > n) {
return 0;
}

if (current == n) {
return 1;
}

if (cache[current] > 0) {
return cache[current];
}

int combinations = dfs(n, current + 1, cache) + dfs(n, current + 2, cache);
cache[current] = combinations;

return combinations;
}
}

/*
Time complexity : O(2^n)
Size of recursion tree will be 2^n

ref: https://leetcode.com/problems/climbing-stairs/solution/
*/
class Solution_recursive {
public int climbStairs(int n) {
if (n <= 0) {
return 0;
}

return dfs(n, 0);
}

private int dfs(int n, int current) {

if (current > n) {
return 0;
}

if (current == n) {
return 1;
}

return dfs(n, current + 1) + dfs(n, current + 2);
}
}

}

• // OJ: https://leetcode.com/problems/climbing-stairs/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int climbStairs(int n) {
int ans = 1, prev = 1;
while (--n) {
ans += prev;
prev = ans - prev;
}
return ans;
}
};

• class Solution:
def climbStairs(self, n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return b

############

class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 1:
return 1
pre, ppre = 1, 1
for i in range(2, n + 1):
tmp = pre
pre = ppre + pre
ppre = tmp
return pre