Designing an optimal configuration for a reconfigurable robot to complete a task is an important issue. This paper proposes an optimization approach for a lattice distortable reconfigurable robot to pursue the best configuration with the least number of modules, and the robot configuration obtained by the approach has enough workspace reachability and structure strength to perform the specific task. This approach is carried out in two steps. In the first step called mechanism design, after establishing the mathematical models by the product of exponential formula for 12 types of lattices, based on the given task workspace, a configuration of an actuator with the least number of lattices is obtained by configuration synthesis method using the genetic algorithm. In the second step called structure design, the K-nearest neighbor method is explored to recognize the removable modules that have the minimum contribution to the overall strength of the robot. Then, an optimal topology configuration of the reconfigurable robot with the least number of modules is obtained by removing the removable modules. A computation example of the configuration optimization of a hexapod robot walking with the tripod gait is performed, and the results show the effectiveness of the proposed optimization approach.