题解 | #切割成本#

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param monsterLength int整型 线段长度
     * @param monsterPoint int整型vector 切割点位置
     * @return int整型
     */
    int attackMonster(int monsterLength, vector<int>& monsterPoint) {
        int numOfPoints = monsterPoint.size() + 2;
        vector<int> points(numOfPoints);
        points[0]=0;
        points[numOfPoints-1]=monsterLength;
        for (int i=1; i<numOfPoints-1; i++) {
            points[i]=monsterPoint[i-1];
        }
        sort(points.begin(),points.end());
        for (int i:points) {
            cout<<i<<"|";
        }
        // monsterPoint加上头尾两个点
        // dp[i][j]表示从第i个点到第j个点，这中间的最小切割成本
        // 相邻点之间切割成本为0，所以dp[i][i+1]=0
        // -1表示该值尚未被初始化
        vector<vector<int>> dp(numOfPoints, vector<int>(numOfPoints, -1));
        for (int i = 0; i < numOfPoints-1; i++) {
            // 一跳邻居的间距为0
            dp[i][i + 1] = 0;
        }
        for (int j = 2; j < numOfPoints; j++) {// 从2跳邻居开始一直到numOfPoints跳邻居
            for (int i = 0; i+j < numOfPoints; i++) {
                // 计算j跳邻居间距dp[i][i+j]
                int minPart=dp[i][i+1]+dp[i+1][i+j];
                for (int k=2; k<j; k++) {
                    int tempPart=dp[i][i+k]+dp[i+k][i+j];
                    if (tempPart<minPart) {
                        minPart=tempPart;
                    }
                }
                dp[i][i+j]=minPart+points[i+j]-points[i];
            }
        }
        for (int i=0; i<numOfPoints; i++) {
            for (int j=0; j<numOfPoints; j++) {
                cout<<dp[i][j]<<",";
            }
            cout<<"|";
        }
        return dp[0][numOfPoints-1];
    }
};

动态规划，monsterPoint加上头尾两个点，对于这N+2个点，开始搜索

dp[i][i+j]表示从第i个点到第i+j个点，这中间的最小切割成本（开区间）

初始化：相邻点之间切割成本为0，所以dp[i][i+1]=0

对j从2开始遍历，j表示“邻居跳数”，从2跳邻居开始算总成本

保证计算 j 跳邻居时，跳数比j小的成本已经全部计算过了

然后对位置i进行遍历

从 i 跳到 i+j 要跳两次，第一次跳到切割点，因此 k 对切割点进行遍历

三次遍历实现最后的算法，复杂度n^3