Sparse dynamic programming II : convex and concave cost functions