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
def countStaircases ( N ) : NEW_LINE INDENT memo = [ [ 0 for x in range ( N + 5 ) ] for y in range ( N + 5 ) ] NEW_LINE for i in range ( N + 1 ) : NEW_LINE INDENT for j in range ( N + 1 ) : NEW_LINE INDENT memo [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT memo [ 3 ] [ 2 ] = memo [ 4 ] [ 2 ] = 1 NEW_LINE for i in range ( 5 , N + 1 ) : NEW_LINE INDENT for j in range ( 2 , i + 1 ) : NEW_LINE INDENT if ( j == 2 ) : NEW_LINE INDENT memo [ i ] [ j ] = memo [ i - j ] [ j ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT memo [ i ] [ j ] = ( memo [ i - j ] [ j ] + memo [ i - j ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT answer = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT answer = answer + memo [ N ] [ i ] NEW_LINE DEDENT return answer NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 7 NEW_LINE print ( countStaircases ( N ) ) NEW_LINE DEDENT