def climb_stairs(n):
    if n == 1:
        return 1

    # Create and initialize lookup table that will store the results of subproblems
    lookup_table = [0 for x in range(n + 1)]  

    # Setting the initial values for the first two steps
    lookup_table[1] = 1  
    lookup_table[2] = 2
    
    # Starting from the third step up to the target step 'n'.
    for i in range(3, n + 1):
        # Fill up the table by summing up previous two values
        lookup_table[i] = lookup_table[i - 1] + lookup_table[i - 2] 
        
    # Return the total number of ways
    return lookup_table[n]  

# Driver code
def main():
    inputs = [1, 4, 3, 5, 6]
    
    for i in range(len(inputs)):
        print(i + 1, ".\t Steps: ",inputs[i],"\n\n\t", \
                         " Number of ways: ", climb_stairs(inputs[i]), sep="") 
            
        print("-" * 100)

if __name__ == '__main__':
    main()