Ответ 1
С большинством проблем с DP я стараюсь найти своеобразное отношение сокращения и покорения. То есть отношение, благодаря которому я могу отрезать размер проблемы с каждым шагом (например, делить и побеждать, но обычно не делит проблему, он просто удаляет небольшую часть). В этой задаче (как и многие другие) мы можем сделать очень простое наблюдение: либо первая точка находится в наборе i точек, либо нет.
Некоторые обозначения: пусть говорят X = {x 1, x 2,..., x k} и обозначают приведенную set X n= {x n, x n + 1,..., x k}.
Таким образом, наблюдение заключается в том, что либо x 1 является одной из точек i, либо это не так. Позвоните в нашу функцию поиска i -set MSD (i, X k) (минимальная сумма расстояний). Мы можем выразить это наблюдение следующим образом:
MSD (i, X k) = либо MSD (i-1, X k-1)) U {x 1 } или MSD (i, X k-1)
Мы можем формализовать "или" часть, реализуя простой способ проверить, какой из этих двух вариантов он на самом деле: мы пробегаем множество X и вычисляем сумму расстояний и проверяем, что на самом деле меньше. Заметим, что эта проверка имеет время работы ki, так как мы наивно проедем через каждую из точек k и возьмем минимальное расстояние от точек в наборе размера i.
Мы делаем два простых наблюдения относительно базовых случаев:
MSD (i, X i) = X i
MSD (0, X n) = {}
Во-первых, при поиске i точек в наборе размера i мы, очевидно, просто возьмем весь набор.
Во-вторых, при поиске точек в наборе мы возвращаем пустой набор. Это индуктивно гарантирует, что MSD возвращает наборы размера i (это верно для случая, когда i=0 и по индукции истинно в соответствии с нашим определением MSD выше).
Что это. Это найдет подходящий набор.
Сложность выполнения сверху ограничена O(ik * step), где шаг - это наша проверка O(ik) сверху. Это связано с тем, что MSD будет работать с параметрами, которые варьируются от 0-i и X 1 - X k, что является суммой ik возможных аргументов.
Это оставляет нам время выполнения O ((ik) 2).
Следующая часть основана на моем понимании вопроса ОП. Я не уверен, что расстояние каждой точки в X от подмножества i-размера является суммой расстояний каждой точки от каждой другой точки подмножества или суммой расстояний каждой точки в X от подмножества сама по себе.
То есть сигма x в X (сумма расстояний x от каждой точки подмножества) ИЛИ сигма x в X (расстояние x от подмножества, которое является минимальным расстоянием от x до любой точки в подмножестве)
Я предполагаю, что последний.
Мы можем сократить время выполнения, оптимизируя проверку O(ik) сверху. Мы замечаем, что элементы фактически отсортированы (хотя и в обратном порядке в этой текущей нотации), так как когда мы добавляем их, мы делаем это всегда с правой стороны. Предполагая, что они будут отсортированы для начала, они будут когда-то из рутинных MSD. Если они не были отсортированы для начала, мы можем сортировать их, что в любом случае будет стоить O(klogk).
После сортировки проверка расстояния каждой точки от точки в наборе будет k * logi, поскольку для каждой точки мы выполняем двоичный поиск. Это дает общее время работы O(ik * klogi + klogk)
= O (k 2 * ilogi).
Наконец, мы можем выразить это как O (k 3 logk). Не самое быстрое решение, но решение.
Я уверен, что есть еще больше оптимизаций, но мой 2c.