Auto-optimization of tensor programs is a crucial technique in deep learning compilers. Traditional tensor program optimization methods rely on the known fixed shape of the tensor, but when inputs of tensor program are only determined at runtime, these traditional methods cannot optimize in advance. To overcome this challenge, we introduce DTuner, a dynamic shape tensor program optimization method based on a constructive algorithmic. By optimizing for a broad variety of potential input forms, DTuner leverages highly focused and quick optimization methods to increase the efficiency of dynamic shape tensor programs, resulting in notable gains in average performance. Specifically, modern advanced GPUs are composed of general-purpose computing cores and specialized computing cores. Since different input shapes can yield varying performance outcomes across different cores, we incorporate a sampling and prediction method in the optimizer to guide the selection of computing cores. Evaluation results demonstrate that our method is 2 to 3 orders of magnitude faster in tuning time compared to the existing state-of-the-art dynamic tensor program optimization methods (Dietcode). Additionally, the optimization performance of the algorithm is comparable to that of state-of-the-art methods. On the Nvidia A100 and Orin platforms, DTuner can enhance the inference performance of commonly used NLP models by up to 27.5%, with average performance improvements of 6% to 7% for dynamic inputs. For typical single dynamic tensor programs, our method can also achieve a maximum performance improvement of 25.7% and an average improvement of 9%.