It was really difficult for me, although I read one very good article and understood the idea of the solution. And I don't know how to solve it without any precalculations. I did a lot of them. Does there exists another solution, without using a big recurrence formula?

You can read about this problem here:
http://www.cse.ust.hk/tcsc/RR/2004-02.ps.gz