At present, large and medium-sized cities in China are faced with the difficulty of parking, and shared parking alleviates this problem. Based on the problem that the heterogeneity of shared parking spaces leads to the difference of customer utility, a random dynamic programming model of cross region allocation has been constructed. The basic principle of the optimal parking allocation mechanism has been proved, and an approximation algorithm has been designed to solve the model. Finally, the effectiveness of the approximation algorithm and the sensitivity of related parameters have been verified by numerical simulation. The results show that the heterogeneity of the parking space has significant influence on the allocation mechanism. Cross region allocation will effectively improve the revenue and parking space utilization. When the heterogeneity is very strong, the platform will not adopt cross region allocation. The results of this paper have provided theoretical support for the allocation decision of shared parking spaces.