Algorithm (Sparse Table, DP)

1. Let $f(i,k)$ denote the minimum cost to have arranged [job[0]] to [job[1]] in $k$ days. Let $D$ be the given job difficulty array.
2. We have $$f(i,k)=\begin{cases} \max\{D[0],…,D[i]\} & \text{if }k=0\\\\ \min_{j\leq k-1\leq i}\{f(j,k-1)+\max\{D[j+1],…,D[i]\}\} & \text{otherwise} \end{cases}.$$
3. Note that the value of $\max\{D[i],…,D[j]\}$ could be using a standard RMQ data structure such as SegmentTree or SparseTable. Because $\max$ is idempotent, SparseTable could achieve $O(1)$ query complexity; thus, we choose it as our RMQ module.

Code

template <class SemiLattice>
struct sparse_table {
  typedef typename SemiLattice::value_type value_type;
  static constexpr auto lat = SemiLattice{};
  const std::vector<value_type> data_view;
  mutable std::vector<std::vector<std::optional<value_type>>> memo;

  sparse_table() = default;

  sparse_table(const std::vector<value_type> & data) : data_view(begin(data), end(data)),
                                                       memo(32 - __builtin_clz(std::size(data)),
                                                            std::vector<std::optional<int>>(size(data))) {}

  template <class InputIterator>
  sparse_table(InputIterator first, InputIterator last) : data_view(first, last),
                                                          memo(32 - __builtin_clz(std::distance(first, last)),
                                                               std::vector<std::optional<int>>(std::distance(first, last))) {}

  value_type f(int k, int i) {
    if (memo[k][i])
      return memo[k][i].value();
    else
      return *(memo[k][i] = [&]() {
        if (k == 0)
          return data_view[i];
        else if (k != 0 and (i + (1ll << (k - 1))) >= data_view.size())
          return lat.unit();
        else
          return lat.mult(f(k - 1, i), f(k - 1, i + (1ll << (k - 1))));
      }());
  };

  value_type range_get(int l, int r) {
    if (l == r) return lat.unit(); 
    const int k = 31 - __builtin_clz(r - l); 
    return lat.mult(f(k, l), f(k, r - (1ll << k)));
  }

};

template <class F>
struct recursive {
  F f;
   template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };

template <typename T> struct max_monoid {
  typedef T value_type;
  value_type unit() const { return std::numeric_limits<T>::lowest(); }
  value_type mult(value_type a, value_type b) const { return std::max(a, b); }
};

class Solution {
 public:
  int minDifficulty(vector<int>& jobDifficulty, int d) {

    const struct {
      mutable optional<int> f[300][10] = {};
    } memo;

    const auto n = size(jobDifficulty);

    auto RMQ = sparse_table<max_monoid<int>>(begin(jobDifficulty), end(jobDifficulty));

    auto f = rec([&, memo = std::ref(memo.f)](auto &&f, int i, int k) -> int {
      if (memo[i][k])
        return memo[i][k].value();
      else
        return *(memo[i][k] = [&] {
          if (k == 0)
            return RMQ.range_get(0, i + 1);
          else
            return [&](int acc = INT_MAX / 2) {
              for (int j = k - 1; j < i; ++j) 
                acc = std::min(acc, f(j, k - 1) + RMQ.range_get(j + 1, i + 1));
              return acc;
            }();
        }());
    });

    return (f(n - 1, d - 1) == INT_MAX / 2) ? -1 : f(n - 1, d - 1);
  }
};