Cheapest order to join stylesheet chunks

Write codeHard40 min

Your task

Your build tool joins a page's stylesheet chunks into a single file. The chunks must stay in their order, because the cascade depends on it. The tool joins 2 neighbouring chunks at a time. Each join costs the size of the chunk it writes.

Write cheapest_join(sizes) that returns the smallest total cost of joining all the chunks into one.

Input and output:

  • sizes: 1 to 300 chunk sizes in bytes, in page order, integers from 1 to 1,000,000,000.
  • Returns an integer.

Rules:

  • A join takes 2 chunks that sit next to each other and replaces them with one chunk in the same place. Its size is the sum of their sizes.
  • Each join costs the size of the chunk it produces.
  • Joins continue until one chunk is left. Return the smallest possible total cost. With 1 chunk, it is 0.

Examples

cheapest_join(sizes: list[int]) -> int
Example 1
Inputcheapest_join([30, 10, 20])
Output90
Example 2
Inputcheapest_join([4, 4, 4, 4])
Output32
Example 3
Inputcheapest_join([100, 1, 1, 100])
Output306