>>409
動的計画法を使うらしい。

https://qiita.com/p_gotcha/items/e2741b12b4f606b96136