One simple solution is called memoization: each time we compute the minimum cost needed to multiply out a specific subsequence, we save it. If we are ever asked to compute it again, we simply give the saved answer, and do not recompute it. Since there are about "n"2/2 different subsequences, where "n" is the number of matrices, the space required to do this is reasonable. It can be shown that this simple trick brings the runtime down to O("n"3) from O(2"n"), which is more than efficient enough for real applications. This is top-down dynamic programming.