How to solve a DP problem that minimizes a sum of cubic powers? I am trying to practice some coding problems and I came upon this problem: 

As electricity prices are soaring, there must be a way to reduce wastage by increasing the utilization of heavy duty machines, such as elevators.
We formulate the problem as follows.
There are $N$ persons $ (p_1,...,p_N)$ waiting in a queue to get into an elevator. By the way, there is only one elevator, and it travels between the ground floor to the sky floor (i.e., there are no other stoppages in between). Also, all persons are waiting on the ground floor.
Just for simplicity, we are concerned only with the utilization of the ground-to-sky journey of the elevator. Each person $p_i$ has a positive weight $w_i$.
The weight capacity of the elevator is $M$. Therefore, all persons may not be carried together. They are carried in several trips. Each person gets into the elevator according to his order in the queue. Meaning, $p_1$ gets in first, then $p_2$ and so on. Suppose at the $t$-th trip, persons $p_j$ through $p_k$ gets into the elevator. The waste factor ($WF$) of the trip $t$ is defined as

$$WF[t]=M-\sum_{i=j}^k(w_i).$$

Your task is to minimize the total waste ($TW$), which is defined as:

$$TW=\sum_{t=1}^{S-1}(WF[t])^3,$$

where $S$ is the total number of trips required to carry all the people from the ground to the sky floor. Note that the $WF$ of the last trip is not included in the $TW$ calculation. 

I got completely stuck here, I figured that this can be solved via DP but I don't know how. Especially with the condition of maintaining the order. 
Full problem can be found in here Problem K: Elevate the Utilization!
The essence of the dynamic programming is to recognize the appropriate subproblems.
Here is a way to formulate the subproblems. Let us compute $dp[i]$, the minimum total waste for weight sequence $w_{i}, w_{i+}, \cdots, w_N$, where $1\le i\lt N$. The wanted minimum total waste of the entire sequence shall be $dp[1]$.
The base cases are $dp[N]=dp[N-1]=\cdots=0$, where $dp[i]=0$ as long as $w_{i} + w_{i+1}+ \cdots+w_{N}\le M$ since the last trip does not produce waste. Let $j$ be the smallest such index.
What about $dp[j-1]$, $dp[j-2]$ and beyond? We note that $dp[k]$ is the minimum of
$$\begin{align}
  dp[k+1] &amp;+ (M-w_k)^3,\\ 
  dp[k+2] &amp;+ (M-(w_k+w_{k+1}))^3,\\
  \cdots\\
  dp[k+t] &amp;+ (M-(w_k+w_{k+1}+\cdots+w_{k+t-1}))^3\\
  \cdots,\\
  \end{align}$$
where the list goes on as long as $w_k+w_{k+1}+\cdots+w_{k+t-1}\le M$.
This recurrence relation enables us to compute $dp[k-1]$ if $dp[k], dp[k-1], \cdots, dp[N]$ are known.
The time complexity of algorithm is about $O(N*N)$.
Java code

The above is an implementation in Java that takes file &quot;elevate.in&quot; as input. Just click &quot;run&quot; to see the result.
Exercises
Here are two exercises based on the same situation to think about.
Exercise 1. (One minute or two.) Suppose the total waste is defined as $$TW=\sum_{t=2}^{S}(WF[t])^3$$ instead. Note that the WF of the first strip instead of the last strip is excluded.
Exercise 2. Suppose the total waste is defined as $$TW=\sum_{t=2}^{S-1}(WF[t])^3$$ instead. Note both the WF of the first strip and the last strip are excluded.