Welcome to Subscribe On Youtube

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[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);
    		}
    	}
    
    }
    
  • // 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
    
    

All Problems

All Solutions