We propose an algorithm for computing the capacity of discrete rewritable storage devices subject to a constraint on the maximal number of rewrite operations. The linchpin is that—although the number of writing strategies is exponential in the maximal number of allowed rewrites—linear functionals of the probabilities they induce on the output space can be efficiently maximized using Dynamic Programming.