In 2003, Chang et al. (Pattern Recognition, 2003, 36(7), 1583-1595) proposed a way to find an optimal one-to-one substitution table using a dynamic programming strategy in image hiding. The present paper introduces a new method which uses the one-to-two substitution table to help with image hiding. First, a square-error matrix with three dimensions was built up. After applying a dynamic programming strategy on the square-error matrix, one can obtain the optimal one-to-two substitution table. According to the experimental results, the new method is capable of offering much better stego-image quality than the LSB substitution method and the one-to-one substitution method.