To cut a wooden board, a sawmill charges proportional to the length of the board. The cost of cutting a single board into many smaller boards will thus depend on the order of the cuts. As an example, lets say cutting a $10m$ board into two pieces costs $10$. Then to cut a $10m$ long board at marked positions $3m$ and $5m$ costs $10+7=17$ if it is first cut at position $3m$ and then at $5m$. On the other hand, if it is cut at $5m$ position first, and then at $3m$, it would cost $10+5=15$. As input, you are given a board of length $n$ with $k$ marks on it. You need to give an algorithm that, given an input length $n$ and a set of $k$ desired cut points along the board, will produce a cutting order with minimal cost in $O(k^c)$ time, for some constant $c$
I'm getting $O(k!)$ complexity :(