Найдите мин. Операции «соединения» для последовательности

Допустим, у нас есть список / массив положительных целых чисел x1, x2,. .., хн. Мы можем выполнить операцию join для этой последовательности, что означает, что мы можем заменить два элемента, которые находятся рядом друг с другом, одним элементом, который является суммой этих элементов. Например:

-> массив / список: [1; 2; 3; 4; 5; 6]

• мы можем объединить 2 и 3 и заменить их на 5;
• мы можем объединить 5 и 6 и заменить их на 11;
• мы не можем соединить 2 и 4;
• мы не можем join 1 и 3 и т. Д.

Основная проблема состоит в том, чтобы найти минимальное количество операций соединения для данной последовательности, после чего эта последовательность будет отсортирована в порядке возрастания.

Примечание: пустые и одноэлементные последовательности сортируются в порядке возрастания

Основные примеры:

• для [4; 6; 5; 3; 9] решение равно 1 (мы соединяем 5 и 3)

• для [1; 3; 6; 5] решение также равно 1 (мы присоединяемся к 6 и 5)

Я ищу алгоритм, который решает эту проблему. Это может быть псевдокод, C, C ++, PHP, OCaml или аналогичный (я имею в виду: я бы понял решение, если бы Вы написали решение на одном из этих языков).