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

}

All Problems

All Solutions