Steganography is the task of embedding a secret message in a cover media (e. g. image, video and voice) such that the stego media is not intuitively separable from the original ones. It is one of the interesting fields of security especially in transferring digital media as the major components of the web sites, emails and any web-based communications. MATRIX embedding is a general approach used in many steganography schemes, especially where the cover size is small e. g. Voice Over IP (VOIP) packets. In this approach, the message is mapped to a series of bits (stego) to replace the same number of low significant bits in the cover. The embedding MATRIX is used for extracting the message by a linear combination of the stego bits. For a given MATRIX and secret message, there are specific series of stego-bits from which the message can be extracted. Embedding is done by an inverse problem to minimize a cost as the difference between the stego and the original bits. Hence, each message has a specific embedding cost based on the MATRIX. In this paper, a method is proposed to find an embedding MATRIX which minimizes the expectation of embedding cost for a uniform distribution of messages. To that end; a dynamic programming algorithm is proposed to efficiently find the expected cost for a given MATRIX. By use of this algorithm, any search method may be used to solve the problem. In this paper, a fast Hill-climbing search strategy is designed to find a local optimum MATRIX in an allowable time.