题解 | #切割成本#

题目描述：
将一条长度为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;

方法一：记忆化搜索
将一段绳子按照切割点数组中的切割点进行切割，每次切割后的子绳子的切割方式与第一次切割的方式是一样的，换句话说采用分治的思想，将一个核心的主问题分解为几个子问题，由子问题的解递推出主问题解的表达式称为状态转移方程，

先对切割点数组进行递增排序，计算每一个子区间的长度时我们需要用到切割点的绳子始端和末端，所以在切割点数组中加入0和绳子长度值
那么，怎么划分子问题呢？如果先从k点切割，则 $def(i+1,k)$ 和 $def(k,j-1)$ 的解都依赖于切割点k和两个边界点，由于分治法中子问题是互相独立的，所以划分问题时，k先不切割，或者说k是最后一个切割的点，求出 $i+1$ 到k的解和k到 $j-1$ 的解，并且在两个子问题解决后，切割序列还剩下 k ，那么我们用两个子问题的解与切割 k 和两个边界的成本最大值即可求出原问题的解。那么 $def( i , j )$ 函数的定义则为，仅切割 i 与 j 之间的点我们能得到的最小成本。如此划分，状态转移方程为： $def( i, j ) = min(min,def( i , k ) + def( k , j )+nums[i]-nums[ k ]+nums[j]-nums[j])$
因为 k 是介于 i 与 j 之间的，那么当 i 与 j 相邻时我们的问题将不能再继续划分。此时按照我们对问题的定义，回归条件就是 i 与 j 之间没有切割点，我们不用切割，切割成本就是0，有了转移方程和回归条件，问题就可以解决了
这里使用记忆数组记录计算过的值，避免重复计算

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param monsterLength int整型 线段长度
     * @param monsterPoint int整型一维数组 切割点位置
     * @return int整型
     */
    private int[][]memory;
    public int attackMonster (int monsterLength, int[] monsterPoint) {
        // write code here
        int n=monsterPoint.length;
        int[]nums=new int[n+2];
        Arrays.sort(monsterPoint);
        //将monsterPoint数组复制到nums数组的1~n-1位置
        System.arraycopy(monsterPoint,0,nums,1,n);
        //将0和绳子的长度值添加到nums数组的首端和尾端
        nums[0]=0;
        nums[n+1]=monsterLength;
        memory=new int[n+2][n+2];
        int res=Max(nums,n+2,0,n+1,memory);
        return res;
    }
    int Max(int[]nums,int len,int start,int end,int[][]memory){
        //base case
        if(start==end-1)return 0;
        //已经被计算过的直接返回
        if(memory[start][end]!=0)return memory[start][end];
        int min=Integer.MAX_VALUE;
        //切割点从start+1到end-1
        for(int k=start+1;k<end;k++){
            min=Math.min(min,Max(nums,len,start,k,memory)+Max(nums,len,k,end,memory)+nums[k]-nums[start]+nums[end]-nums[k]);
        }
        memory[start][end]=min;
        return min;
    }
}

复杂度：
时间复杂度：递归函数每次操作的平均复杂度为 $O(n)$ ,区间数为 $图片说明$ ，最终复杂度为 $图片说明$
空间复杂度：取决于记忆数组的大小,所以是 $图片说明$ (n为切割点数组的大小）

方法二：动态规划
方法一为自顶向下的记忆化搜索，可以转化为自底向上的动态规划,将前者的递归换成后者的递推 $dp[i][j]$ 表示 $monsterPoint(i...j)$ 之间的最小切割成本,k作为切割点只能取 $[i+1,j-1]$
边界条件是 $i+1==j$ 时， $dp[i][j]=0，$ 也就是没有切割点时最小切割成本为0
状态转移方程：

图片说明

$dp[0][n-1]$ 状态是由 $dp[i][k]$ 和 $dp[k][j]$ 递推来的， $i+1<=k<=j-1$ ;那么要得到 $dp[0][n-1]$ ，从 $dp$ 表中 $i$ 值从 $n-2$ 递减到0， $j$ 值由 $i+2$ 递增到 $n-1$ 推演即可

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param monsterLength int整型 线段长度
     * @param monsterPoint int整型一维数组 切割点位置
     * @return int整型
     */
    public int attackMonster (int monsterLength, int[] monsterPoint) {
        // write code here
        int n=monsterPoint.length;
        Arrays.sort(monsterPoint);
        //dp[i][j]表示monsterPoint(i...j)之间的最小切割成本,k作为切割点只能取[i+1,j-1]
        int[][]dp=new int[n+2][n+2];
        int[]nums=new int[n+2];
        System.arraycopy(monsterPoint,0,nums,1,n);
        //添加0和monsterLength切割点
        nums[0]=0;
        nums[n+1]=monsterLength;
        int len=nums.length;
        //dp:i为start,j为end,k为切割点
        for(int i=len-2;i>=0;i--){
            for(int j=i+2;j<len;j++){ 
                //如果i,j相邻，切割成本为0
                if(i==j-1)dp[i][j]=0;
                else{
                int min=Integer.MAX_VALUE;
                for(int k=i+1;k<j;k++){
                    min=Math.min(min,dp[i][k]+dp[k][j]+nums[k]-nums[i]+nums[j]-nums[k]);
                }dp[i][j]=min;
                }
            }
        }return dp[0][len-1];
    }
}

复杂度：
时间复杂度：三层循环，时间复杂度为 $图片说明$
空间复杂度： $dp$ 数组的大小为 $n^{2}$ ，空间复杂度为 $图片说明$