Skip to main content

Climb Stairs With Minimum Moves

1. You are given a number n, representing the number of stairs in a staircase.

2. You are on the 0th step and are required to climb to the top.

3. You are given n numbers, where ith element's value represents - till how far from the step you 

     could jump to in a single move.  You can of-course fewer number of steps in the move.

4. You are required to print the number of minimum moves in which you can reach the top of 

     staircase.

Note -> If there is no path through the staircase print null.

Input Format

A number n

.. n more elements

Output Format

A number representing the number of ways to climb the stairs from 0 to top.


Constraints

0 <= n <= 20

0 <= n1, n2, .. <= 20

Sample Input

10

3

3

0

2

1

2

4

2

0

0

Sample Output

4


Solution:

import java.io.*;

import java.util.*;


public class Main {


    public static void main(String[] args) throws Exception {

        // write your code here

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] A = new int[n];

        for(int i=0;i<n;i++)

            A[i] = sc.nextInt();

        System.out.println(minClimb(n,A));

    }


    public static int minClimb(int n,int[] A){

        if(n <= 0) return 0;

        Integer[] arr = new Integer[n+1];

        arr[n] = 0;

        for(int i=n-1;i>=0;i--){

            if(A[i] == 0) continue;

            int min = 25;

            for(int j=A[i];j>0;j--){

                if((i+j>n) || (arr[i+j] == null)) continue;

                min = Math.min(min,arr[i+j]);

                

            }

            if(min != 25)

                arr[i] = min + 1;

        }

        return arr[0];

    }


}

Comments

Must Read:

Programming using Java Hands On - Control Structures | Bill Generation

Bill Generation Tom went to a movie with his friends in a multiplex theatre and during break time he bought pizzas, puffs and cool drinks.  Consider   the following prices :  Rs.100/pizza Rs.20/puffs Rs.10/cooldrink Generate a bill for What Tom has bought. Sample Input 1: Enter the no of pizzas bought:10 Enter the no of puffs bought:12 Enter the no of cool drinks bought:5 Sample Output 1: Bill Details No of pizzas:10 No of puffs:12 No of cooldrinks:5 Total price=1290 ENJOY THE SHOW!!! Result Description Summary of tests *Note: All the test cases might not have same weightage +------------------------------+ | 6 tests run/ 6 tests passed | +------------------------------+

Data Formats ( XML & JSON ) XML AND JSON | Generate XSD 2

  Generate XSD 2 Generate XSD for the following XML document <?xml version="1.0" encoding="UTF-8"?> <!--  <!DOCTYPE  hotels  SYSTEM "hotel.dtd"> --> <hotels> <hotel> <ID>1</ID> <Name> TAJ GANJ </Name> <Stars>3</Stars> <Facilities>Restaurant,Parking,Internet</Facilities> <Address>Taj Ganj,FFatehabad Road Agra Uttar Pradesh 282001</Address> <Type>budget</Type> <Available>true</Available> </hotel> <hotel> <ID>2</ID> <Name> TAJ EXOTICA </Name> <Stars>5</Stars> <Facilities>Indian therapies,Yoga and meditation,Spaindulges,Parking</Facilities> <Address>CalwaddoBenaulim, Salcete Goa 403716</Address> <Type>luxury</Type> <Available>false</Available> </hotel> <hotel> <ID>3</ID> <Name> VIVANTA by TAJ </Name> <Stars>3<...

Programming using Java Hands On - Control Structures | Print Customer Details

Print Customer Details Help Mr.Ben who is a programmer, in developing a registration form on console. Customers will not just input data, but also view the details once he/she finishes the registration.  Sample Input 1: Enter your name:Jany Enter age:25 Enter gender:Female Hailing from:Mexico Sample Output 1: Welcome, Jany Age:25 Gender:Female City:Mexico Result Description Summary of tests *Note: All the test cases might not have same weightage +------------------------------+ | 5 tests run/ 5 tests passed | +------------------------------+

Accenture TFA Quiz | Part 2

  Question  26 Correct Marked out of 1 Flag question Question text What will be the output of the following Java code? public class ApplicationTester { public static void main(String[] args) { int[] array = {11,22,33,44,55,11}; int searchNumber = 11, position=999; for(int index=0; index < array.length; index++) { if(searchNumber == array[index]) { position = index; } } System.out.println(position); } } Choose the most appropriate option. Select one: a.  0 b.  5   c.  1 d.  6 Feedback The correct answer is: 5 Question  27 Incorrect Marked out of 1 Flag question Question text Predict the line of code Abstract class Base1 { protected void getDetails() { System.out.println("Base method"); } public Abstract void demomethod(); } Abstract class Base2 extends Base1 { public Abstract void samplemethod(); } class Derived extends Base2 { //Line1 } Select one: ...

Software Engineering Concepts Configuration Management And Version Control Configuration Management And Version Control Quiz 1

 

Web Technology HTML 5 HTML 2 | Quiz 1

 Web Technology       HTML 5            HTML 2               Quiz 1  

UNIX Introduction to Unix | Post-Quiz

 UNIX  Introduction to Unix  Post-Quiz  Feedback Congratulations! You have passed by securing more that 80%. Question  1 Correct Mark 1.00 out of 1.00 Flag question Question text  What is the default maximum number of processes that can exist in Unix? Select one: a.  unlimited b.   32768           c.   4096        d.  1024          Feedback Your answer is correct. The correct answer is:  32768         Question  2 Correct Mark 1.00 out of 1.00 Flag question Question text Single user mode shell has _____ prompt.  Select one: a.   $ Normal user  b.  % Admin user c.  ~ Home user d.  # Root user    Feedback Your answer is correct. The correct answer is: # Root user  Question  3 Correct Mark 1.00 out of 1.00 Flag question Question text Predict the output for the following...

Min Cost In Maze Traversal

1. You are given a number n, representing the number of rows. 2. You are given a number m, representing the number of columns. 3. You are given n*m numbers, representing elements of 2d array a, which represents a maze. 4. You are standing in top-left cell and are required to move to bottom-right cell. 5. You are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 motion. 6. Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom-       right cell). 7. You are required to traverse through the matrix and print the cost of path which is least costly. Input Format A number n A number m e11 e12.. e21 e22.. .. n * m number of elements Output Format The cost of least costly path. Constraints 1 <= n <= 10^2 1 <= m <= 10^2 0 <= e1, e2, .. n * m elements <= 1000 Sample Input 6 6 0 1 4 2 8 2 4 3 6 5 0 4 1 2 4 1 4 6 2 0 7 3 2 2 3 1 5 9 2 4 2 7 0 8 5 1 Sample Output 23 Solution: import java.io.*; import...

Programming using Java Running case study - Requirement 1 / 6 | State Board of Cricket Council –V1.0 *

  State Board of Cricket Council –V1.0 * State Board of Cricket Council   State Board of Cricket Council (SBCC) is one of the leading cricket selection academies in the state . They are in need of an automated system that should manipulate the player details provided and also find the players who have secured star rating between a specific range from the database. You being their software consultant have been approached to develop a pilot java application which can be used by the  admin for the above mentioned requirement . UserInterface.java package  com.sbcc.main; import  com.sbcc.model.*; import  java.util.*; import  java.lang.*; import  com.sbcc.skeletonvalidator.SkeletonValidator; public   class   UserInterface  {      public   static   Player   pl ;      public   static   void   main ( String []  args ) {        ...

Subscribe to Get's Answer by Email