The maintenance strategies optimization can play a key role in the industrial systems, in particular to reduce the related risks and the maintenance costs, improve the availability, and the reliability. Spare part demands are usually generated by the need of maintenance. It is often dependent on the maintenance strategies, and a better practice is to deal with these problems simultaneously. This article presents a stochastic dynamic programming maintenance model considering multi-failure states and spare part inventory. First, a probabilistic maintenance model called hidden semi-Markov model with aging factor is used to classify the multi-failure states and obtain transition probabilities among multi-failure states. Then, spare parts inventory cost is integrated into the maintenance model for different failure states. Finally, a double-layer dynamic programming maintenance model is proposed to obtain the optimal spare parts inventory and the optimal maintenance strategy through which the minimum total cost can be achieved. A case study is used to demonstrate the implementation and potential applications of the proposed methods.