All problems

Phone Menu Layout

Medium · dynamic programming

A help line greets callers with a menu. There are n topics, always listed in the same fixed order, and freq[i] is how many callers per day want topic i.

The menu is built as a tree of questions:

  1. Pick any one topic from the list to ask about first.
  2. Callers who want a topic that comes earlier in the list than that one are sent on to a smaller menu, built in the same way from just those earlier topics.
  3. Callers who want a topic that comes later are sent to another smaller menu, built the same way from just the later topics.
  4. A menu with no topics left is empty.

A caller presses one button per menu they pass through, counting the menu that asks about their topic. A topic asked about in the very first menu takes 1 press, a topic asked about in the next level takes 2, and so on.

Return the smallest possible total number of presses per day over all callers, over every way of building the menu.

Examples

Example 1

Input: freq = [3, 1, 4]

Output: 13

Ask about the last topic first (4 x 1 = 4). Send the others to a menu that asks about the first topic (3 x 2 = 6), then the middle one (1 x 3 = 3). The total is 13, and every other layout is at least 14.

Example 2

Input: freq = [5]

Output: 5

One topic, asked about first: 5 x 1 = 5.

Example 3

Input: freq = [1, 1, 1, 1, 1, 1, 1]

Output: 17

A perfectly balanced menu: one topic at level 1, two at level 2 and four at level 3, so 1 + 4 + 12 = 17.

Constraints