In this paper, we propose new motion schemes for a biped robot to walk up and down a staircase using dynamic encoding algorithm for searches (DEAS) for optimization. Ascending and descending a staircase are scheduled by four phases for convenience of motion generation. Each phase mimics the natural gait of a human being and is easy to analyze and implement. Optimal trajectories of 10 joint motors in a lower extremity of a humanoid are computed to simultaneously satisfy stability conditions, walking constraints, and energy efficiency requirements, and the zero moment point condition. The performance of uDEAS is compared to genetic algorithm in finding 13 parameters with the result that uDEAS requires only 17 seconds, which is 12 times faster. The feasibility of the proposed motion schemes is validated with computer simulations and experiments successfully carried out for a small humanoid robot.