这个题的标签是动态规划。

然而我并没有想出dp的做法，只有按照大多数人的打表做法AC。

然后我大概翻了15页的提交记录，除了看不到的，其他都是打表的做法。

所以这个题目真的可以用dp做吗？

还是其实是一个打表模板题？