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

Shell Script to find sum, product and average of given numbers - The Coding Shala

Home >> Scripting >> Sum, product and average Shell Script to find the sum, product, and the average of given numbers Read four integer numbers from the user and find the sum, product, and average of these four numbers? Code:  #! / bin / bash echo "enter four integers" read a b c d sum =$(echo "$a + $b + $c + $d" | bc - l) average=$(echo "$sum / 4" | bc - l) product=$(echo "$a * $b * $c * $d" | bc - l) echo "sum = $sum" echo "Average = $average" echo "Product = $product" Other Posts You May Like Shell script to print sum of the digits of a number Shell Script to print number in descending order Shell script to find out biggest number from three numbers Shell script to find out factorial of a number Shell Script to create a simple calculator Please leave a comment below if you like this post or found some error, it will help me to improve my content.
Read more

LeetCode - Bulb Switcher Solution - The Coding Shala

Image
Home >> LeetCode >> Bulb Switcher LeetCode - Bulb Switcher Solution In this post, we will discuss LeetCode's Bulb Switcher Problem and its solution in Java. There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds. Example: Input: 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After the first round, the three bulbs are [on, on, on]. After the second round, the three bulbs are [on, off, on]. After the third round, the three bulbs are [on, off, off].  So you should return 1 because there is only one bulb is on. Practice this problem on LeetCode(Click Here). Java Solution of Bulb Switcher Problem Let's
Read more

Anti Diagonals - The Coding Shala

Image
Home >> Interview Questions >> Anti Diagonals Anti Diagonals Java Solution Give an N*N square matrix, return an array of its anti-diagonals. Look at the example for more details. Example: Input: 1 2 3 7 8 9 4 5 6 Return the following : [ [1], [2, 4], [3, 5, 7], [6, 8], [9] ] Input : 1 2 3 4 Return the following : [ [1], [2, 3], [4] ] Anti Diagonals Java Solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 public class Solution { public ArrayList < ArrayList < Integer >> diagonal ( ArrayList < ArrayList < Integer >> A ) { ArrayList < ArrayList < Integer >> ans = new ArrayList < ArrayList < Integer >>(); int N = A . size (); int i = N - 1 ; while ( i >= 0 ){ ArrayList < Integer > tmp = new ArrayList < Integer >();
Read more

Sorting the Sentence LeetCode Solution - The Coding Shala

Home >> LeetCode >> Sorting the Sentence  In this post, we will learn how to solve LeetCode's Sorting the Sentence Problem and will implement its solution in Java. Sorting the Sentence Problem A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of lowercase and uppercase English letters. A sentence can be shuffled by appending the 1-indexed word position to each word then rearranging the words in the sentence. For example, the sentence "This is a sentence" can be shuffled as "sentence4 a3 is2 This1" or "is2 sentence4 This1 a3". Given a shuffled sentence s containing no more than 9 words, reconstruct and return the original sentence. Example 1: Input: s = "is2 sentence4 This1 a3" Output: "This is a sentence" Explanation: Sort the words in s to their original positions "This1 is2 a3 sentence4", then remove the numbers. Example 2: Input:
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