# Maximal Profit of 'legal' cutting of a board

I'm facing this problem for some time now, I've tried a greedy approach yet I result to trying a DP-ish approach, only to get stuck at a standstill.

Given a board of length $$n$$, and an increasing monotonic "price" function $$p:\mathbb{N}\rightarrow\mathbb{R}^+$$, an acceptable partition (Notated by $$X=\{x_1,x_2,\ldots x_m\}$$) of the board to $$m\leq n$$ pieces is defined by: $$x_1, x_2, \ldots x_m \in \mathbb{N}^+$$ $$\sum^{m}_{i=1}x_i=n$$ the profit of an acceptable partition is defined to be the sum:$$\sum^{m}_{i=1}p(x_i)$$

The problem asks to describe an efficient algorithm to find an acceptable partition which produces the maxiaml profit, out of all acceptable cuts.

I've tried to apply the solution to the "Woodcutter's problem" to this situation, yet the "Woodcutter's Problem" doesnt apply when a price/profit function is introduced.

Let $$OPT[i]$$ denote the maximum profit that can be attained by partitioning a board of length $$i$$ (according to $$p$$).
Then $$OPT[0] = 0$$ since the only acceptable partition has $$m=0$$. For $$i = 1, \dots, n$$: $$OPT[i] = \max_{j=1, \dots, i} \left( p(j) + OPT[i-j] \right).$$
The optimal profit is then in $$OPT[n]$$. The partition itself can be reconstructed by retracing the dynamic programming choices that led to the value in $$OPT[n]$$.