题解 | #切割成本#

算法思想一：动态规划

解题思路：

可以用动态规划解决这个问题，

1、创建辅助数组dp，其中用 $dp[i][j]$ 表示 $monsterPoint[i]...monsterPoint[j]$ 之间（前闭后开）的切割点的最小成本，只要完善dp数组，最后 $dp[i][n+1]$ 就是要求的最小切割成本和。
2、通过在原切割点数组中加入首尾点，然后一起排序。然后从0结点开始找 i 到 j 的子区间，三层遍历，

第一层找到子区间的长度

第二层找到子区间开始的位置

第三层找到子区间的切割点
其中，状态转移原理如下：取中间一个切割点，切割点左边耗费最少成本+切割点右边耗费最少成本+区间最右边的值-区间最左边的值。

代码展示：

Python版本

class Solution:
    def attackMonster(self , monsterLength , monsterPoint ):
        # write code here
        n = len(monsterPoint)
        # dp数组
        dp = []
        for i in range(n+2):
            dp.append([0 for _ in range(n+2)])
        tmp = [0, monsterLength] + monsterPoint
        # 排序
        tmp.sort()
        # 步长
        for i in range(2, n+2):
            # 子区间起始点
            for j in range(1, n-i+3):
                dp[j][j+i-1] = float('inf')
                # 子区间各个中断点
                for k in range(j, j+i-1):
                    # 状态转移方程
                    dp[j][j+i-1] = min(dp[j][j+i-1], dp[j][k]+dp[k + 1][j + i -1] + tmp[j + i -1] - tmp[j - 1])
        return dp[1][n + 1]

JAVA版本

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param monsterLength int整型 线段长度
     * @param monsterPoint int整型一维数组 切割点位置
     * @return int整型
     */
    public int attackMonster (int monsterLength, int[] monsterPoint) {
        // write code here
        // 数组排序
        Arrays.sort(monsterPoint);
        int n =  monsterPoint.length;
        // dp数组
        int[][] dp = new int[n+2][n+2];
        // 
        int [] len = new int[n+2];
        for(int i=1;i<n+1;i++){
            len[i] = monsterPoint[i-1];
        }
        len[0]=0;
        len[n+1] = monsterLength;
        for (int i = 2; i <= n+1; i++) { //步长
            for (int j = 0; j <= n+1-i; j++) { //子区间起始点
                int initialMin=Integer.MAX_VALUE;
                for (int k = j+1; k < i+j; k++) {    //子区间各个间隔点
                    int tempV=dp[j][k]+dp[k][j+i]+len[j+i]-len[j];
                    if(initialMin>tempV){
                        initialMin=tempV;
                    }
                }
                dp[j][j+i]=initialMin;
            }
        }
        return dp[0][n+1];
    }
}

复杂度分析

时间复杂度 $O(n^3)$ ：三层遍历时间

空间复杂度 $O(n^2)$ ：辅助数组dp、tmp占用空间

算法思想二：动态规划优化

解题思路：

方法一动态规划复杂度太高，可以利用平行四边形优化的思想来优化动态规划。
1、建立另一个辅助数组，数组中记录子区间各个中断点的下标，第三层循环就可以被大大缩短。

2、利用dp2来限制最后一层遍历的循环区间

3、根据平行四边形优化思想优化后的状态转移方程：

$dp[i][j]=min\{dp[i][k-1]+dp[k][j]\}+w[i][j] ,k>i\&\&k<=j$
其中,如果 $w[i][j]+w[i'][j']<=w[i][j']+w[i'][j], i<=i'<=j<=j'$ ,满足凸四边形不等式(本题显然满足且等号一直成立)

并且 $w[i'][j]<=w[i][j'],i<=i'<=j<=j'$ ,满足区间区间包含关系单调(本题显然满足).

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

代码展示：

C++版本

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<vector<int> > dp1(n + 5, vector<int>(n + 5, 0));
        vector<vector<int> > dp2(n + 5, vector<int>(n + 5, 0));
        vector 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^2)$

空间复杂度 $O(n^2)$ ：辅助数组占用空间