用C ++查找在k天内完成工作的最低难度总和

假设我们有一个称为作业的数字列表，另一个值为k。现在我们要在k天内完成所有工作。这些工作必须按照给定的顺序执行，并且每天我们必须完成一项任务。作业i的难度存储在作业[i]中，并且一天完成一份作业列表的难度将是当天执行的最大难度。因此，我们必须找到在k个不同日期完成工作的最小难度总和。

因此，如果输入像jobs = [2，3，4，6，3] k = 2，那么输出将是8，首先我们要做[2]，然后做[3，4，6，3]。因此难度为2 +（3、4、6、3）的最大值= 8。

范例（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e6;
int dp[505][15];
int dfs(int start, int k, vector <int>& v){
   if(start >= v.size()){
      return k == 0 ? 0 : inf;
   }
   if(k < 0)
      return inf;
   if(dp[start][k] != -1)
      return dp[start][k];
   int ret = inf;
   int val = 0;
   for(int i = start; i < v.size(); i++){
      val = max(val, v[i]);
      ret = min(ret, val + dfs(i + 1, k - 1, v));
   }
   return dp[start][k] = ret;
}
int solve(vector<int>& jobs, int k) {
   memset(dp ,-1, sizeof dp);
   return dfs(0, k, jobs);
}
int main(){
   vector<int> v = {2, 3, 4, 6, 3};
   int k = 2;
   cout << solve(v, k);
}

输入值

{2, 3, 4, 6, 3}, 2

8