Total number of different staircase that can made from N boxes | Java program to find the total number of different staircase that can made from N boxes ; Function to find the total number of different staircase that can made from N boxes ; DP table , there are two states . First describes the number of boxes and second describes the step ; Initialize all the elements of the table to zero ; Base case ; When step is equal to 2 ; When step is greater than 2 ; Count the total staircase from all the steps ; Driver Code
import java . util . * ; class GFG { static int countStaircases ( int N ) { int [ ] [ ] memo = new int [ N + 5 ] [ N + 5 ] ; for ( int i = 0 ; i <= N ; i ++ ) { for ( int j = 0 ; j <= N ; j ++ ) { memo [ i ] [ j ] = 0 ; } } memo [ 3 ] [ 2 ] = memo [ 4 ] [ 2 ] = 1 ; for ( int i = 5 ; i <= N ; i ++ ) { for ( int j = 2 ; j <= i ; j ++ ) { if ( j == 2 ) { memo [ i ] [ j ] = memo [ i - j ] [ j ] + 1 ; } else { memo [ i ] [ j ] = memo [ i - j ] [ j ] + memo [ i - j ] [ j - 1 ] ; } } } int answer = 0 ; for ( int i = 1 ; i <= N ; i ++ ) answer = answer + memo [ N ] [ i ] ; return answer ; } public static void main ( String [ ] args ) { int N = 7 ; System . out . println ( countStaircases ( N ) ) ; } }