题解 | #切割成本#

思路：

题目的主要信息：

给定一个一个长为 $x$ 的线段，和一系列切割点
切割点的成本等于切割后产生的两段线段的和
要求所有切割点的最小切割成本和

方法一：动态规划
具体做法：
我们可以用动态规划解决这个问题，创建辅助数组dp，其中用 $dp[i][j]$ 表示 $monsterPoint[i...j)$ 之间（前闭后开）的切割点的最小成本，只要完善dp数组，最后的 $dp[i][n+1]$ 就是我们要求的最小切割成本和。
我们通过在原切割点数组中加入首尾点，然后一起排序。然后从0结点开始找 $i$ 到 $j$ 的子区间，三层遍历，第一层找到子区间的长度，第二层找到子区间开始的位置，第三层找到子区间的切割点。
其中，状态转移原理如下：取中间一个切割点，切割点左边耗费最少成本+切割点右边耗费最少成本+区间最右边的值-区间最左边的值。

class Solution {
public:
    int attackMonster(int monsterLength, vector<int>& monsterPoint) {
        int n = monsterPoint.size();
        vector<vector<int> > dp(n + 2, vector<int>(n + 2, 0));
        vector<int> temp = {0, monsterLength};
        for(int i = 0; i < n; i++)
            temp.push_back(monsterPoint[i]);
        sort(temp.begin(), temp.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;
                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] + temp[j + i -1] - temp[j - 1]);
            }
        }
        return dp[1][n + 1];
    }
};

复杂度分析：

时间复杂度： $O(n^3)$ ，三层遍历
空间复杂度： $O(n^2)$ ，辅助数组dp和temp

方法二：动态规划优化
具体做法：
方法一动态规划复杂度太高，我们可以利用空间换时间的思想来优化它。
建立另一个辅助数组，数组中记录子区间各个中断点的下标，第三层循环就可以被大大缩短。
详细可见图示，利用dp2来限制最后一层遍历的循环区间：
图片说明

class Solution {
public:
    int attackMonster(int monsterLength, vector<int>& monsterPoint) {
        int n = monsterPoint.size();
        vector<vector<int> > dp1(n + 5, vector<int>(n + 5, 0));
        vector<vector<int> > dp2(n + 5, vector<int>(n + 5, 0));
        vector<int> temp = {0, monsterLength};
        for(int i = 0; i < n; i++)
            temp.push_back(monsterPoint[i]);
        n++;
        for(int i = 1; i <=n; i++){ //初始化辅助矩阵
            dp1[i][i] = 0;
            dp2[i][i] = i;
        }
        sort(temp.begin(), temp.end()); //排序
        for(int i = 1; i < n; i++){ //步长
            for(int j = 1; j + i <= n; j++){ //子区间起始点
                int Min = INT_MAX;
                int index = 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] + temp[i + j] - temp[j - 1] < Min){
                         Min = dp1[j][k] + dp1[k + 1][i + j] + temp[i + j] - temp[j - 1];
                         index = k; //记录下标
                     }
                dp1[j][i + j] = Min;
                dp2[j][i + j] = index;
            }
        }
        return dp1[1][n];
    }
};

复杂度分析：

时间复杂度： $O(n^2)$ ，属于动态规划的平行四边形优化，从 $O(n^3)$ 优化到了 $(n^2)$
空间复杂度： $O(n^2)$ ，多个辅助数组，最大为 $O(n^2)$