Блог пользователя laimancode

Автор laimancode, 10 лет назад, По-английски

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.

Полный текст и комментарии »

Теги dp
  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится