Sparse dynamic programming I: linear cost functions