  Dynamic programming is an important optimization technique, but designing
efficient dynamic programming algorithms can be difficult for even professional
programmers. Thinning, a technique developed for systematically deriving
efficient dynamic programming algorithms, has received much attention in
studies because of its effectiveness for a large class of problems. Despite the
success of thinning in theory, its practical usage is still limited because (1)
applying thinning requires mathematical and algorithmic background, and (2)
applying thinning solely may not be enough to generate algorithms as efficient
as proposed by human experts.
  In this paper, we propose two approaches, MetHyl and MetHyl+, to resolve both
problems. First, MetHyl automates the application of thinning via program
synthesis and thus eliminates the burden to the user for applying thinning.
Second, MetHyl+ integrates three rules into MetHyl that optimize three
important factors on the time complexity of dynamic programming algorithms that
are ignored by thinning, and thus make it able to automatically generate
expert-level dynamic programming algorithms on many tasks.
  We evaluate our approaches on 37 tasks related to 16 optimization problems
collected from Introduction to Algorithm, a popular textbook for algorithm
courses. The results show that MetHyl+ achieves exponential speed-ups on 97.3%
of tasks with an average time cost of less than one minute. Moreover, MetHyl+
generates algorithms that are as efficient as the reference programs provided
by human experts on 70.3% of tasks.
