The fuel cells have high potential and superiority in future green transportations. The hybridization of the fuel cells with other energy storage devices such as the lithium-ion batteries and supercapacitors provides an effective way to alleviate the burden and prolong the lifespan of the fuel cells. The designs of topology and management strategy are important for fuel cell vehicles. This paper presents an improved power splitting strategy for hybrid propulsion systems by using multiple-grained velocity prediction. In this paper, the dynamic programming strategy is presented to realize optimal power splitting for different power sources. Moreover, the Markov prediction method is employed for the multiple-grained vehicle velocity prediction. In order to verify the proposed method in the hybrid propulsion system, a semi-physical platform is established to realize the hardware-in-loop simulation. The case study of different hybrid electric propulsion structures is analyzed and discussed. The system hydrogen consumption cost and electricity price of different hybrid propulsion systems are compared under the urban dynamometer driving schedule. The paper systematically compares the power splitting strategy used in different hybrid propulsion structures, in hopes of providing some inspirations to the design and control of the hybrid propulsion system.