The processing of simple least-significant-bit (LSB) substitution embeds the secret image in the least significant bits of the pixels in the host image. This processing may degrade the host image quality so significantly that grabbers can detect that there is something going on in the image that interests them. To overcome this drawback, an exhaustive least-significant-bit substitution scheme was proposed by Wang et al. but it takes huge computation time. Wang et al. then proposed another method that uses a genetic algorithm to search ''approximate'' optimal solutions and computation time is no longer so huge. In this paper, we shall use the dynamic programming strategy to get the optimal solution. The experimental results will show that our method consumes less computation time and also gets the optimal solution.