Dist (B) + Dist (A-B)

Question

A - последовательность различных элементов, B - подпоследовательность A, A-B - все элементы в A, но не в B Dist (A) = Sum | a (i) -a (i + 1) | от i = 1 до n-1 Найдите подпоследовательность B такую, что Dist (B) + Dist (A-B) минимален Я знаю, что это можно решить с помощью динамического программирования, но не могу понять, как ... кто-нибудь с ответом ???

Answer 1

Давайте добавим по одному элементу за раз, и давайте пометим B и AB так, чтобы последний добавленный элемент находился в B. Если мы N элементов в A, нам нужно отслеживать N множеств B_i, так что B_i является наименьшимстоимостное решение, где последним элементом в AB является a_i (множество B_0 является множеством A, так что AB пусто).Когда мы добавляем a_n, мы обновляем стоимость каждого из B_i, добавляя | a_n + a_ {n-1} |и пусть B_ {n-1} будет множеством (A - B_k) + {a_n}, где k is имеет минимум | a_n - a_k |.