Board cutting problem
To me, the way the cutting cost analogy is unnatural. I'm going to work with an equivalent problem instead. Additionally, I'll think about the task in reverse, combining pieces instead of cutting.

An equivalent problem:


  Given a sequence of integers $s_0,s_1,\ldots,s_k$. We want to find the order of adding up all the integers such that the cost of this process is minimize. The add operation only works on each adjacent pair in the sequence and will replace the pair with its sum. The cost of each add operation is the resulting sum.


I'll think about the problem of finding lowest cost first. The order of adding can be traced back if you have the algorithm to find the lowest cost.

Define $M(i,j)$ to be the lowest cost of this process on the subsequence


  $s_i,s_{i+1},s_{i+2}\ldots,s_{j-2},s_{j-1},s_j$


where $0 \le i \le j \le k$

We can then formulate $M(i,j)$ in terms of smaller problems as follows:


  $M(i,j) = \Sigma_{y=i}^{j} s_y + \min\limits_{x \ldotp i \leq x &lt; j} \{M(i,x) + M(x+1,j) \}$


for the case that $j-i&gt;2$

I'll leave the base case of $j-i \le 2$ and the order of which $M(i,j)$ to calculate first for reader to work out.



The algorithm has to calculate $M(i,j)$ for every $0 \le i \le j \le k$ and each time it does that, it has to iterate over $x$. Thus, the time complexity is $O(k^3)$