Lately, there is an increased interest in the analysis of music score facsimiles, aiming at automatic digitization and recognition. Noise, corruption, variations in handwriting, non-standard page layouts and notations are common problems affecting especially the centuries-old manuscripts. Starting from a facsimile, the current state-of-the-art methods binarize the image, detect and group the staff lines, then remove the staff lines and classify the remaining symbols imposing rules and prior knowledge to obtain the final digital representation. The first steps are critical for the performance of the overall system. Here we propose to handle binarization, staff detection and noise removal by means of dynamic programming (DP) formulations. Our main insights are: a) the staves (the 5-groups of staff lines) are represented by repetitive line patterns, are more constrained and informative, and thus we propose direct optimization over such patterns instead of first spotting single staff lines, b) the optimal binarization threshold also is the one giving the maximum evidence for the presence of staves, c) the noise, or background, is given by the regions where there is insufficient stave pattern evidence. We validate our techniques on the CVC-MUSCIMA(2011) staff removal benchmark, achieving the best error rates (1.7%), as well as on various, other handwritten score facsimiles from the Renaissance.