<p>我们可以在<code>O(d*N)</code>时间复杂度中使用<code>O(N)</code>空间,使用堆栈</p>
<p><strong>说明:</strong></p>
<p><strong>dp配方:</strong></p>
<p>这个公式与<a href="https://stackoverflow.com/a/64541503/6741053">here</a>几乎没有什么不同。因为我们可以使用堆栈计算到目前为止在当天<code>d</code>发现的最大难度的成本</p>
<pre><code>dp[i][d] - represent minimum difficulty that can be achieved considering d days and first i jobs.
</code></pre>
<p><strong>重复性:</strong></p>
<p>有3种情况:</p>
<ol>
<li><code>ith</code>作业是d天的唯一作业,其余所有作业在{<cd3>}天之前完成</李>
<li>我们尝试添加到当前日期,并查看<code>A[i]</code>是否比当前已完成的任何先前更高难度的工作<code>j</code>难度更大<code>d</code></li>
<li>有一项难度更高的工作<code>j</code>我们在今天前面看到的<code>d</code></李>
</ol>
<hr/>
<pre><code>dp[i][d] = min( A[i] + dp[i-1][d-1], // ith job is the only job on day d
A[i] + (dp[j][d] - A[j]), // or we try adding to current day and see if A[i] has more difficulty than any previous higher difficulty job j already completed on present day
dp[j][d] // or there is some higher difficulty job `j` we saw previously on present day `d`.
)
</code></pre>
<p><strong>C++实现:</strong></p>
<p>我们维护堆栈以计算迄今为止所看到的最高难度作业<code>j</code>。正如我们在递归中看到的,我们只需要前一天的值来计算当天的值,所以我们在那里节省了空间</p>
<pre><code>int minDifficulty(vector<int>& A, int D) {
int jobs = A.size();
if (jobs < D) return INT_MAX ; // impossible to do atleast 1 job everyday
int max_difficulty = *max_element(A.begin(), A.end()) + 1;
vector<int> prv_day(jobs, max_difficulty), curr_day(jobs);
for (int days = 0; days < D; ++days) {
vector<int> stack;
for (int i = days; i < jobs; i++) {
curr_day[i] = i > 0 ? prv_day[i - 1] + A[i] : A[i]; // start fresh day with first job as ith
while (!stack.empty() && A[stack.back()] <= A[i]) {
int j = stack.back(); stack.pop_back();
curr_day[i] = min(curr_day[i], curr_day[j] - A[j] + A[i]); // or we try extending and see if A[i] has more difficulty than any previous job j on present day
}
if (!stack.empty()) {
curr_day[i] = min(curr_day[i], curr_day[stack.back()]); // or there is some higher difficulty job we saw previously
}
stack.push_back(i);
}
swap(prv_day, curr_day);
}
return prv_day[jobs - 1];
}
</code></pre>
<p><strong>时间复杂性:</strong></p>
<p>对于每一天,我们都要花费<code>O(N)</code>时间来计算。所以时间复杂度是<code>O(d*N)</code>。堆栈中的项最多被推送和弹出<code>O(N)</code>次</p>
<p><strong>额外空间复杂性:</strong></p>
<p><code>O(N)</code>存储当前和以前的状态,以及<code>O(N)</code>存储堆栈</p>