原题题目
思路分析
1335. 工作计划的最低难度 其实在我拿到这道题的时候 一眼也就看出来大致方向是怎么做的 这道题如果大家是按照难度做的话 那么其实和上面一道题 分割字符串III很相似的 所以这道题我在调试+代码15min左右也就完成AC了
中心解题题意
首先我们抛开这道题背后的什么工作难度 什么几项任务的文字除开 我们直接进入正题
直戳重心就是:
我们需要把数组分割成 d 个子数组 每个子数组最大的数就代表了这个子数组的数值 然后我们需要把所有子数组（等于d个代表数相加）加起来 我们需要求这几个数的最小和
思路分析
首先第一步 就是先把每个子数组的代表数求出来
这里我用的是二维数组来记录 dp[jobDifficultySize+1][jobDifficultySize+1]
dp[start][end] start是子数组的开始位置 end是结束位置 然后dp[start][end]代表就是这个子数组的代表数
然后 主要算法就是 dp[start][end] = fmax(dp[start][end],dp[start][end-1])
接着就是 我们再用一个二维数组记录 ret[d][jobDifficultySize]
然后前面的ret[day][end] day就表示当前是第几天 end就表示完成到什么位置了
然后 我们的天数肯定是一天一天增加的 那么我们的ret[day]的一行肯定就要与ret[day-1]的一行相关的
就我举个例子 比如我们想求ret[第二天][结束任务位置5号位] 即ret[1][4]
那么我们怎么求这个呢 看下面的代码可能你一下就会明白了
ret[1][4] = INT_MAX;
for(start = 0;start < 4;start++)
{
if(ret[0][start] != INT_MAX) //这里的INT_MAX表示无法工作到此处ret[1][4] = fmin(ret[0][start] + dp[start+1][end],ret[1][4]);
}
对的 就是我们在第一天的基础上 再往上加 我们的工程量（结束位置就是4) 就等于我们需要求的
如果我们的这个位置 比如第一天往上加的起点处都访问不了 那说明肯定就不能再往上加工程量了
最后我们就return dp[d-1][jobDifficultySize-1] 表示第d天 和 结束任务位置 jobSize
如果是INT_MAX 则说明 无法做工作到此处 在第d天 返回-1即可
代码实现（首刷自解）
int minDifficulty(int* jobDifficulty, int jobDifficultySize, int d){
int dp[jobDifficultySize+1][jobDifficultySize+1],start,end,count;memset(dp,0,sizeof(dp));for(start=0;start<jobDifficultySize;start++){
for(end = start;end<jobDifficultySize;end++){
dp[start][end] = jobDifficulty[end];if(end > start) dp[start][end] = fmax(dp[start][end],dp[start][end-1]);}}int ret[d+1][jobDifficultySize+1];for(count = 0;count<d;count++){
for(end = 0;end<jobDifficultySize;end++){
if(!count) ret[count][end] = dp[0][end];else{
ret[count][end] = INT_MAX;for(start = 0;start<end;start++){
if(ret[count-1][start] != INT_MAX)ret[count][end] = fmin(ret[count-1][start] + dp[start+1][end],ret[count][end]);} }}}if(ret[d-1][jobDifficultySize-1] != INT_MAX) return ret[d-1][jobDifficultySize-1];else return -1;
}