Quadrupedal robots are designed to walk over complex terrains (e.g., hills, rubble, deformable terrains, etc.) However, training quadruped robots to walk on complex terrains is a challenge. One difficulty is the problem caused by the sensors. Exteroceptive sensors such as cameras are cheap and convenient, but cameras are limited in some environments (e.g., sewers without lights). Training a legged robot using proprioceptive can avoid the aforementioned situation. This research proposes a method combining terrain curriculum and adaptive submodularity. The legged robot is able to adaptively select actions over complex terrains without exteroceptive sensors. Adaptive submodularity is utilized to predict the terrain and take sequential actions with theoretical guarantees. The experiments demonstrate the proposed approach has fewer prediction errors than the random approach.