1547.Minimum-Cost-to-Cut-a-Stick

这是一道典型的区间型的DP。对于[i,j]这段区间，我们考虑如何砍下第一刀？显然下刀的位置可以是cuts[i+1],cuts[i+2],...,cuts[j-1]。我们假设在位置k下刀，那么这一刀的代价就是[i,j]的程度，接下来问题就转为了两个小区间[i,k]和[k,j]的问题。所以状态转移方程是：

dp[i][j] = min{dp[i][k]+dp[k][j]+cuts[j]-cuts[i]} for k=i+1,i+2,...,j-1

边界条件是对于任何长度为1的区间[i,i+1]，不需要下刀，代价就是0.