题目描述

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

方法一 区间DP

解题思路

定义数组表示之间切割点的最小成本.为了计算每一个子区间的长度，需要向中添加边界点0和绳子长度,然后对所有切割点进行排序.
在切割时,对每个区间,假设第个点是最后一个切割的点,那么我们先求出和,代表完成了切割第个点之前所有步骤,并且已经取得了最小值,然后再加上切割第个点的成本即为最后切割时能够获得的最小值.即状态转移方程为,其中,.
为了枚举所有区间,实现区间DP,我们可以选择枚举所有的步长和区间起始点,并且把数组初始值设为无穷大.
对所有区间枚举完之后,求得的即为所求的最小切割成本.

图片说明

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param monsterLength int整型 线段长度
     * @param monsterPoint int整型vector 切割点位置
     * @return int整型
     */
    int attackMonster(int monsterLength, vector<int>& monsterPoint) {
        int n = monsterPoint.size();
        // dp[i][j]:monsterPoint[i...j)之间的最小切割成本
        vector<vector<int> > dp(n + 2, vector<int>(n + 2, 0));
        // 将起始点和结束点加入切割点中方便计算区间长度
        vector<int> point = {0, monsterLength};
        for(int i = 0; i < n; i++)
            point.push_back(monsterPoint[i]);
        // 对切割点排序
        sort(point.begin(), point.end());
        // 枚举所有区间
        for(int i = 2; i <= n + 1; i++){ // 枚举步长
            for(int j = 1; j + i - 1 <= n + 1; j++){ // 枚举子区间起始点
                dp[j][j + i - 1] = INT_MAX; // dp数组初始值设置为无穷大
                // 枚举所有k值以得到dp[i][j]的最小值
                // k:最后进行切割的点
                for(int k = j; k < j + i - 1; k++)
                    dp[j][j + i- 1] = min(dp[j][j + i - 1], dp[j][k] + dp[k + 1][j + i -1] + point[j + i -1] - point[j - 1]);
            }
        }
        // 返回答案
        return dp[1][n + 1];
    }
};

复杂度分析

  • 时间复杂度：需要对切割点排序,时间复杂度为,然后需要枚举所有区间,对每个区间,需要枚举所有区间内的切割点,时间复杂度为,所以总的时间复杂度为
  • 空间复杂度：数组的空间复杂度为

方法二 平行四边形优化

解题思路

虽然本题并没有卡时间,方法一中的DP方法虽然时间复杂度较高仍然能够AC,但是方法一的DP算法可以被优化.这在动态规划中是经典的一类问题,称为平行四边形优化,优化后时间复杂度可以从降到.
这类问题的状态转移方程可以写为
其中,如果,满足凸四边形不等式(本题显然满足且等号一直成立);

图片说明

并且,满足区间区间包含关系单调(本题显然满足).

图片说明

那么设的最小值为,则有,因此我们可以缩小枚举的范围从而降低时间复杂度.具体地说,在枚举每一个区间时,我们可以仅仅枚举本区间的所有切割点而不需要枚举本区间内的所有连续值来获得切割成本的最小值.

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param monsterLength int整型 线段长度
     * @param monsterPoint int整型vector 切割点位置
     * @return int整型
     */
    int attackMonster(int monsterLength, vector<int>& monsterPoint) {
        int n = monsterPoint.size();
        // dp1[i][j]:monsterPoint[i...j)之间的最小切割成本
        vector<vector<int> > dp1(n + 3, vector<int>(n + 3, 0));
        // dp2[i][j]:monsterPoint[i...j)之间达到最小切割成本时的最后切割点下标
        vector<vector<int> > dp2(n + 3, vector<int>(n + 3, 0));
        // 将起始点和结束点加入切割点中方便计算区间长度
        vector<int> point = {0, monsterLength};
        for(int i = 0; i < n; i++)
            point.push_back(monsterPoint[i]);
        // 初始dp数组
        for(int i = 1; i <= n + 1; i++){
            dp1[i][i] = 0;
            dp2[i][i] = i;
        }
        // 对切割点排序
        sort(point.begin(), point.end());
        // 枚举所有区间
        for(int i = 1; i < n + 1; i++){ // 枚举步长
            for(int j = 1; j + i - 1<= n; j++){ // 枚举子区间起始点
                int Min = INT_MAX; // 最小切割成本初始值设置为无穷大
                int index = 0; // 最小切割成本时最后切割点初始化为0
                // 枚举区间范围内所有切割点
                for(int k = dp2[j][i + j - 1]; k <= dp2[j + 1][i + j]; k++)
                    // 根据状态转移方程更新最小值和切割点坐标
                     if(dp1[j][k] + dp1[k + 1][i + j] + point[i + j] - point[j - 1] < Min){
                         Min = dp1[j][k] + dp1[k + 1][i + j] + point[i + j] - point[j - 1];
                         index = k;
                     }
                dp1[j][i + j] = Min;
                dp2[j][i + j] = index;
            }
        }
        // 返回答案
        return dp1[1][n + 1];
    }
};

复杂度分析

  • 时间复杂度：枚举区间时需要的时间复杂度,经过平行四边形优化,每次枚举仅需要检查常数个自区间内的切割点,所以总的时间复杂度为
  • 空间复杂度：使用了两个大小为的dp数组,所以空间复杂度为