Find the number of ways to reach Kth step in stair case | Java implementation of the approach ; Function to return the number of ways to reach the kth step ; Create the dp array ; Broken steps ; Calculate the number of ways for the rest of the positions ; If it is a blocked position ; Number of ways to get to the ith step ; Return the required answer ; Driver code
class GFG { static final int MOD = 1000000007 ; static int number_of_ways ( int arr [ ] , int n , int k ) { if ( k == 1 ) return 1 ; int dp [ ] = new int [ k + 1 ] ; int i ; for ( i = 0 ; i < k + 1 ; i ++ ) dp [ i ] = - 1 ; for ( i = 0 ; i < n ; i ++ ) dp [ arr [ i ] ] = 0 ; dp [ 0 ] = 1 ; dp [ 1 ] = ( dp [ 1 ] == - 1 ) ? 1 : dp [ 1 ] ; for ( i = 2 ; i <= k ; ++ i ) { if ( dp [ i ] == 0 ) continue ; dp [ i ] = dp [ i - 1 ] + dp [ i - 2 ] ; dp [ i ] %= MOD ; } return dp [ k ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 3 } ; int n = arr . length ; int k = 6 ; System . out . println ( number_of_ways ( arr , n , k ) ) ; } }