Cheapest order to join stylesheet chunks
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]) -> intExample 1
Input
cheapest_join([30, 10, 20])Output
90Example 2
Input
cheapest_join([4, 4, 4, 4])Output
32Example 3
Input
cheapest_join([100, 1, 1, 100])Output
306