Скажем, у нас есть список/массив положительных целых чисел x1, x2,..., xn. Мы можем выполнить операцию объединения в этой последовательности, что означает, что мы можем заменить два элемента, которые находятся рядом друг с другом с одним элементом, который является суммой этих элементов. Например:
- > массив/список: [1; 2; 3; 4; 5; 6]
- мы можем присоединиться к 2 и 3 и заменить их на 5;
- мы можем присоединиться к 5 и 6 и заменить их на 11;
- мы не можем соединить 2 и 4;
- мы не можем присоединяться к 1 и 3 и т.д.
Основная проблема заключается в том, чтобы найти минимальные операции объединения для данной последовательности, после чего эта последовательность будет сортироваться в порядке возрастания.
Примечание: пустые и одноэлементные последовательности сортируются в порядке возрастания.
Основные примеры:
-
для [4; 6; 5; 3; 9] решение равно 1 (мы присоединяемся к 5 и 3)
-
для [1; 3; 6; 5] решение также 1 (мы присоединяемся к 6 и 5)
Я ищу, это алгоритм, который решает эту проблему. Это может быть в псевдокоде, C, С++, PHP, OCaml или аналогичном (я имею в виду: я бы понял решение, если вы написали решение на одном из этих языков).