很明显的一个区间dp
首先把首尾两点加入读进去的数组中，排序
就像正常的区间dp一样
第一重循环：子区间长度
第二重循环：子区间开头位置
第三重循环：子区间的中间断的点
时间复杂度![： ](https://www.nowcoder.com/equation?tex=N%5E%7B3%7D "图片标题") 

class Solution {
public:
    /**
     *
     * @param monsterLength int整型 怪兽长度
     * @param monsterPoint int整型vector 怪兽攻击点位置
     * @return int整型
     */
    int attackMonster(int monsterLength, vector<int>& monsterPoint) {
        // write code here
        int n = monsterPoint.size();
        monsterPoint.push_back(0);
        monsterPoint.push_back(monsterLength);
        sort(monsterPoint.begin(), monsterPoint.end());
        int dp[305][305];
        memset(dp,0,sizeof(dp));
        for(int len=2;len<=n+1;len++)
        {
            for(int i=1;i+len-1<=n+1;i++)
            {
                dp[i][i+len-1]=0x3f3f3f3f;
                for(int k=i;k<=i+len-1;k++)
                {
                    dp[i][i+len-1]=min(dp[i][i+len-1],
                                       dp[i][k]+dp[k+1][i+len-1]+monsterPoint[i+len-1]-monsterPoint[i-1]);
                }
            }
        }
       return dp[1][n+1];
    }
};

比较好的做法是用平行四边形优化，这个题想对大多数同学友好一些，所以没卡必须要优化时间
平行四边形优化证明：https://blog.csdn.net/lmyclever/article/details/6677683

class Solution {
public:
    /**
     *
     * @param monsterLength int整型 怪兽长度
     * @param monsterPoint int整型vector 怪兽攻击点位置
     * @return int整型
     */
    int attackMonster(int monsterLength, vector<int>& monsterPoint) {
        // write code here
        int n = monsterPoint.size();
        monsterPoint.push_back(0);
        monsterPoint.push_back(monsterLength);
        sort(monsterPoint.begin(), monsterPoint.end());
        int dp[305][305],p[305][305];
        n++;
        for(int i=1; i<=n; i++)
        {
            dp[i][i] = 0;
            p[i][i] = i;
        }

        for(int len=1; len<n; len++)
        {
            for(int i=1; i+len<=n; i++)
            {
                int end = i+len;
                int tmp = 0x3f3f3f3f;
                int k = 0;
                for(int j=p[i][end-1]; j<=p[i+1][end]; j++)
                {
                    if(dp[i][j] + dp[j+1][end] + monsterPoint[end] - monsterPoint[i-1] < tmp)
                    {
                        tmp = dp[i][j] + dp[j+1][end] + monsterPoint[end] - monsterPoint[i-1];
                        k = j;
                    }
                }
                dp[i][end] = tmp;
                p[i][end] = k;
            }
        }
        return dp[1][n];
    }
};