Sparse dynamic programming I : linear cost functions