The presentation is devoted to the description of new tools for decision tree study based on extensions of dynamic programming: sequential optimization of decision trees relative to different criteria, study of relationships between two cost functions, and between a cost function and uncertainty of decision trees. We consider one application - comparison of 16 heuristics for decision tree optimization relative to different cost functions. We discuss extensions of some of these results to the case of decision rules.