# Question

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

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

# 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

• 
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[0] = 1; // to make dp[2] correct when adding up
dp[1] = 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);
}
}

}

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

class Solution {
public int climbStairs(int n) {
int a = 0, b = 1;
for (int i = 0; i < n; ++i) {
int c = a + b;
a = b;
b = c;
}
return b;
}
}

• // 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


• func climbStairs(n int) int {
a, b := 0, 1
for i := 0; i < n; i++ {
a, b = b, a + b
}
return b
}

• function climbStairs(n: number): number {
let p = 1;
let q = 1;
for (let i = 1; i < n; i++) {
[p, q] = [q, p + q];
}
return q;
}


• /**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
let a = 0,
b = 1;
for (let i = 0; i < n; ++i) {
const c = a + b;
a = b;
b = c;
}
return b;
};


• class Solution {
/**
* @param Integer $n * @return Integer */ function climbStairs($n) {
if ($n <= 2) { return$n;
}
$dp = [0, 1, 2]; for ($i = 3; $i <=$n; $i++) {$dp[$i] =$dp[$i - 2] +$dp[$i - 1]; } return$dp[\$n];
}
}

• impl Solution {
pub fn climb_stairs(n: i32) -> i32 {
let (mut p, mut q) = (1, 1);
for i in 1..n {
let t = p + q;
p = q;
q = t;
}
q
}
}