题解引用

这类极小化极大问题，其实是一种最坏情况下的博弈，通常都可以使用动态规划解决。动态规划的思路是，将大范围的问题先分割成小范围的问题，先解决小范围情况下的极小化，再通过状态转移函数由小范围问题组成大范围问题。
如在这一题中，在分割1-n这个大区间时，因为答案可能在任何一个子区间出现，所以我们不需要考虑它是如何分割成小区间的，只需要取所有分割点代价的最小值即可。