题解 | #切割成本#
切割成本
http://www.nowcoder.com/practice/5c5fa5bf2a9942fcb1a3844d715087b9
切割成本
描述
将一条长度为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;
第一种方案：
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;
方法一
思路分析
本题采用动态规划即自下而上的办法，给定一长度为n的线段，由于不确定切割点的位置，因此找到所有的整数端点作为切割点，设置二维数组$array[i][j]$用于存储两个切割点之间的切割成本，为了找到每一线段的切割，设置线段的开始位置与结束位置作为切割点。采用自下而上的办法，即先算一个切割点到其他切割点的切割成本。设置$array[i][k]+array[k+1][j]+f[i]-f[j]$表示某一区间内切割点为k的最小切割成本。其状态转移方程如下：
图解
核心代码
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<int> f;
vector<vector<int> > array(n+2);
for(int i=0;i<n+2;i++)
{
array[i].resize(n+2);
}
for(int i=0;i<n;i++)
{
f.push_back(monsterPoint[i]);
}
f.push_back(0);
f.push_back(monsterLength);//首尾节点加入切割数组中
sort(f.begin(),f.end());//对切割数组进行排序
int res=operation(n,array,f);
return res;
}
int operation(int n,vector<vector<int> > &array,vector<int>& f)
{
for(int i=0;i<n+1;i++)
{
array[i][i+1]=0;//单独的一段不可切割
}
for(int i=2;i<n+2;i++)//子区间长度
{
for(int j=1;j<n-i+3;j++)//子区间开始位置
{
array[j][j+i-1]=INT_MAX;
for(int m=j;m<j+i-1;m++)//找到切割点
{
array[j][j+i-1]=min(array[j][j + i - 1], array[j][m] + array[m + 1][j + i -1] + f[j + i -1] - f[j - 1]);
//切割点左边切割成本+切割点右边切割成本+区间右侧值-区间左侧值
}
}
}
return array[1][n+1];//第一个切割点到最后一个切割点的最小成本
}
}; 复杂度分析 - 时间复杂度：三层嵌套循环，最大时间复杂度为$O(n^3)$
- 空间复杂度：借助于一个大小为$n+2$的辅助数组用于存储切割点，借助一个大小为$(n+2)^2$的辅助数组用于存储区间切割成本，因此空间复杂度为$O(n^2)$
方法二
思路分析
二分法，建议再找一种办法。
核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param monsterLength int整型 线段长度
* @param monsterPoint int整型vector 切割点位置
* @return int整型
*/
vector<int >res;
vector<int> f;
int attackMonster(int monsterLength, vector<int>& monsterPoint) {
// write code here
int n = monsterPoint.size();
for(int i=0;i<n;i++)
{
f.push_back(monsterPoint[i]);
}
f.push_back(0);
f.push_back(monsterLength);//首尾节点加入切割数组中
sort(f.begin(),f.end());//对切割数组进行排序
int left=0;
int right=n+1;//最后一个位置切割点
int mid;
if((left+right)%2==0)
mid=(left+right)/2;
else
mid=(left+right)/2+1;
res.push_back(monsterLength);
operation(0,mid-1,f[mid]);
operation(mid+1,n+1,monsterLength-f[mid]);
int m=res.size();
int ans=0;
for(int i=0;i<m;i++)
ans+=res[i];
return ans;
}
void operation(int left,int right,int length)
{
if((right-left)==1)
{
res.push_back(length);
return;
}
int mid;
if((left+right)%2!=0)
mid=(left+right)/2;
else
mid=(left+right)/2+1;
res.push_back(f[mid]+length-f[mid]);
operation(left,mid-1,f[mid]);
operation(mid+1,right,length-f[mid]);
}
}; 算法自然分析 文章被收录于专栏
在解决问题的同时，不断与人交流学习，通过牛客各式各样的题目，学习分享。
