描述

将一条长度为x的线段切成若干段，切割点已给出，每次切割的成本为切割后产生的两段线段长度之和，求最小的切割成本。

示例

输入：20,[2,5,10,18]

返回值：45

说明：线段长为20，切割点为[2,5,10,18]。
第一种方案：
1.先切开第一个点，成本为2+18=20
2.切开第二个点，成本为3+15=18
3.切开第三个点，成本为5+10=15
4.切开第四个点，成本为8+2=10
总成本为：20 + 18 + 15 + 10 = 63;
第二种方案：
1.先切开第一个点，成本为5+15=20
2.切开第二个点，成本为2+3=5
3.切开第三个点，成本为5+10=15
4.切开第四个点，成本为8+2=10
总成本为：20 + 5 + 15 + 10 = 50;

       本题采用动态规划即自下而上的办法，给定一长度为n的线段，由于不确定切割点的位置，因此找到所有的整数端点作为切割点，设置二维数组$array[i][j]$用于存储两个切割点之间的切割成本，为了找到每一线段的切割，设置线段的开始位置与结束位置作为切割点。采用自下而上的办法，即先算一个切割点到其他切割点的切割成本。设置$array[i][k]+array[k+1][j]+f[i]-f[j]$表示某一区间内切割点为k的最小切割成本。其状态转移方程如下：

                                     

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();
        vector<int> f;
        vector<vector<int> > array(n+2);
        for(int i=0;i<n+2;i++) 
        {
          array[i].resize(n+2);
        }
         for(int i=0;i<n;i++) 
        {
          f.push_back(monsterPoint[i]);
        }
        f.push_back(0);
        f.push_back(monsterLength);//首尾节点加入切割数组中
        sort(f.begin(),f.end());//对切割数组进行排序
        int res=operation(n,array,f);
        return res;
    }
    int operation(int n,vector<vector<int> > &array,vector<int>& f)
    {
        for(int i=0;i<n+1;i++)
        {
            array[i][i+1]=0;//单独的一段不可切割
        }
        for(int i=2;i<n+2;i++)//子区间长度
        {
            for(int j=1;j<n-i+3;j++)//子区间开始位置
            {
                array[j][j+i-1]=INT_MAX;
                for(int m=j;m<j+i-1;m++)//找到切割点
                {
                    array[j][j+i-1]=min(array[j][j + i - 1], array[j][m] + array[m + 1][j + i -1] + f[j + i -1] - f[j - 1]);
                    //切割点左边切割成本+切割点右边切割成本+区间右侧值-区间左侧值
                }
            }
        }
        return array[1][n+1];//第一个切割点到最后一个切割点的最小成本
    }
};

复杂度分析

• 时间复杂度：三层嵌套循环，最大时间复杂度为$O(n^3)$
• 空间复杂度：借助于一个大小为$n+2$的辅助数组用于存储切割点，借助一个大小为$(n+2)^2$的辅助数组用于存储区间切割成本，因此空间复杂度为$O(n^2)$

二分法，建议再找一种办法。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param monsterLength int整型 线段长度
     * @param monsterPoint int整型vector 切割点位置
     * @return int整型
     */
    vector<int >res;
    vector<int> f;
    int attackMonster(int monsterLength, vector<int>& monsterPoint) {
        // write code here
        int n = monsterPoint.size();
         for(int i=0;i<n;i++) 
        {
          f.push_back(monsterPoint[i]);
        }
        f.push_back(0);
        f.push_back(monsterLength);//首尾节点加入切割数组中
        sort(f.begin(),f.end());//对切割数组进行排序
        int left=0;
        int right=n+1;//最后一个位置切割点
        int mid;
        if((left+right)%2==0)
            mid=(left+right)/2;
        else 
             mid=(left+right)/2+1;
        res.push_back(monsterLength);
        operation(0,mid-1,f[mid]);
        operation(mid+1,n+1,monsterLength-f[mid]);
        int m=res.size();
        int ans=0;
        for(int i=0;i<m;i++)
            ans+=res[i];
        return ans;
        
    }
    void operation(int left,int right,int length)
    {
        if((right-left)==1)
        {
            res.push_back(length);
            return;
        }
        int mid;
        if((left+right)%2!=0)
            mid=(left+right)/2;
        else 
             mid=(left+right)/2+1;
        res.push_back(f[mid]+length-f[mid]);
        operation(left,mid-1,f[mid]);
        operation(mid+1,right,length-f[mid]);
    }
    
};