CareerCup

The cost of each cut is determined by the longer piece in last cut. For example,1st cost is always 15. 1st cut at 9, then the next cut cost is 9(9-0>15-9). 2nd cut at 5, the next cost is 5. So each time choose the point which is nearest to the middle point.

Each time, chosing median point is the right answer.

Nope median(greedy strategy) does not work. You will have to use Dynamic Programming

a dp solution could be :
let the log cuts to be made be L[1],L[2],...,L[k] s.t. L[1]<L[2]<...<L[k]<L.

1. set L[0]=0 and L[k+1]=L
2. let c[i][j] be the min cost to completely cut a log of wood that starts at groove i and end at groove j, then we need to find a groove between i and j, say m such that after cutting at m we have two logs which are minimum in terms of their cost themselves. also note that j>i+1 for a 1 length cannot be cut and hence if j<=i+1 c[i][j] should be 0 for it.

thus ,
c[i][j] = ((L[j]-L[i]) + min(c[i][m] + c[m][j]) for all i<m<j and j>i+1)
and 0 otherwise.

create a top-down recursive function and the min cost shall get saved at c[0][k+1]. The order can be found by storing the value of m at each c[i][j].

this is a O(n^3) solution.