laimancode's blog

By laimancode, 8 years ago, In English

hi everyone! my first post

Problem: a wooden rod is separated into pieces of length L1, L2, ..., Ln. Cutting a rod of length L into two pieces costs L. But we want to cut the rod into n-1 pieces. There is an optimal order of cuts that produces the minimum cost. (can be calculated by dynamic programming)

Is the minimum cost always smallest when the pieces are in order from smallest to greatest? I think it is, but do not know how to prove.

Read more »

Tags dp
  • Vote: I like it
  • +13
  • Vote: I do not like it