CRISPR-based lineage tracing has emerged as a promising approach for studying cell transformations during development and disease progression. However, the high ratio of cells to mutations, coupled with missing data from silencing or dropout, challenges tree reconstruction, even with the leading method Startle, which is based on Star Homoplasy Parsimony (SHP). Here, we present Star-CDP, the first dynamic programming algorithm that solves the SHP problem within a constrained search space \(\varSigma \) defined by subsets of cells from which a solution cell lineage tree must draw its clades. When \(\varSigma \) is the power set, Star-CDP is an exact exponential algorithm with time complexity \(O(nm|\varSigma |^2)\) , where n and m denote the number of cells and sites, respectively. We show how to build clade constraints that are polynomially-sized and effective in practice. We also develop algorithms to efficiently count, sample, and build consensus trees from all solutions to the clade-constrained SHP problem, motivated by the challenges in producing consistent phylogenetic signal across the tree with current lineage tracing technologies. In simulations, Star-CDP’s strict consensus typically achieves the best f1-score for the majority of model conditions studied, except when the proportion of missing data from silencing versus dropout reached 100%. Lastly, we analyzed lineage tracing data from a mouse model of lung adenocarcinoma, finding that Star-CDP produced plausible trees, often lowering the number of migration and reseeding events needed to explain metastases compared to Startle. Star-CDP is available on Github: https://github.com/molloy-lab/Star-CDP .