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
    }
}

70 - Climbing Stairs

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions