LeetCode - Climbing Stairs Java - The Coding Shala

Home >> LeetCode >> Climbing Stairs

LeetCode Climbing Stairs Problem

In this post, we will see how to solve the leetcode climbing stairs problem in Java.

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
Practice on Leetcode Click Here

Climbing Stairs Java Solution

Approach 1:

Using dynamic programming.

Java Program: 

class Solution {
    public int climbStairs(int n) {
        if(n<=2) return n;
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for(int i=2;i<n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n-1];
    }
}

Approach 2:
Using Recursion.
Java Program: 

class Solution {
    HashMap<Integer, Integer> map = new HashMap<>();
    public int climbStairs(int n) {
        if(map.containsKey(n)){
            return map.get(n);
        }
        
        int result;
        if(n<=2) result = n;
        else{
            result = climbStairs(n-1)+climbStairs(n-2);
        }
        map.put(n,result);
        return result;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

By

Comments

Post a Comment

Popular Posts from this Blog

Time Complexity, Space Complexity, Asymptotic Notations - The Coding Shala

Image
Home >> Algorithms >> Time and space complexity Time Complexity, Space Complexity, and Asymptotic Notations Time complexity describes the time taken by an algorithm and space complexity describes the memory used by an algorithm. Asymptotic Notations are languages that allow us to calculate time complexity and space complexity. Big O is most commonly used for time complexity or analysis of algorithms. Time Complexity In Computer Science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input. The time complexity of an algorithm is commonly expressed using big O notation, which excludes coefficients and lowers order terms.[From Wikipedia] In a simple way we can say how much time our code takes to execute.  So, How to calculate the running time of an algorithm? We can have three cases to analyze an algorithm: Worst Case Average Case Best C...
Read more

Java Program to Reverse a String using Stack - The Coding Shala

Home >> Java Programs >> Reverse a String using Stack  Hey there, welcome back to another post. In this post, we will learn how to reverse a string using a stack in Java. Java Program to Reverse a String using Stack As we know,  Stack data structure follows last in the first out (LIFO), so by using stack we can reverse a given string. For example:  Input: hello output: olleh After storing into stack Stack -> o l l e h Now print stack -> olleh Java Program:  import java.util.Scanner; import java.util.Stack; /** * https://www.thecodingshala.com/ */ public class Main { public static String doReverse(String str) { Stack<Character> stack = new Stack<>(); // push all characters into stack for ( int i = 0; i < str.length(); i++) { stack.push(str.charAt(i)); } // pop characters from stack and build s...
Read more

Java Method Overloading - The Coding Shala

Image
Home >> Learn Java >> Java Method Overloading Java Method Overloading Java class can have more than one method with the same name but different in parameters, known as Method Overloading. Question: What is the use of method overloading? Answer:  Suppose we want to perform some operation like an addition but addition can be performed between two numbers, three numbers or two floats or more. So instead of using different methods, we use the same name of the method with different parameters. This can increase the readability of the program. Method overloading can be achieved by changing numbers of arguments or by changing the data types. Example of Method Overloading in Java The following example explains Method Overloading: //Method Overloading example class Addition { public int add ( int a , int b ){ return a + b ; } public int add ( int a , int b , int c ){ return a + b + c ; ...
Read more

New Year Chaos Solution - The Coding Shala

Home >> Programming Questions >> New Year Chaos New Year Chaos Problem Solution In this post, you will learn how to solve New Year Chaos Problem and implement its solution in Java. Problem:   It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment from at the front of the line to at the back.  Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others.  For Example, if n=8 and Person 5 bribes Person 4, the queue will look like this: 1,2,3,5,4,6,7,8. Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state. Inpu...
Read more

Number of Steps to Reduce a Number to Zero LeetCode Solution - The Coding Shala

Home >> LeetCode >> Number of Steps to Reduce a Number to Zero  In this post, we will learn how to solve LeetCode's Number of Steps to Reduce a Number to Zero problem and will implement its solution in Java. Number of Steps to Reduce a Number to Zero Problem Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it. Example 1: Input: num = 14 Output: 6 Explanation:  Step 1) 14 is even; divide by 2 and obtain 7.  Step 2) 7 is odd; subtract 1 and obtain 6. Step 3) 6 is even; divide by 2 and obtain 3.  Step 4) 3 is odd; subtract 1 and obtain 2.  Step 5) 2 is even; divide by 2 and obtain 1.  Step 6) 1 is odd; subtract 1 and obtain 0. Practice this problem on LeetCode . LeetCode - Number of Steps to Reduce a Number to Zero Java Solution Approach 1 A simple iterative approach using the loop. Java Program:  ...
Read more