This is homework-related, but I've been trying to come up with something on and off for days now, and I can't find anything.
There's this tree you need in n pieces, each with length Ln. It costs x currency to saw a piece of length x in two pieces. Now, with all Ln known, I need a dynamic programming algorithm (saving information inbetween that can be used later) to calculate the minimum cost of the job.
I can't figure it out. As an example, we got the computation of a binomial coefficient. That I understood. You keep a table in memory, and add two cells each time. With this problem, I can't think of anything (table, array) to save that will help later on. All I can think of right now is exhaustive search.
Any hint would be appreciated.
Thanks! |
