algorithm - 距离(B)+ 距离(A-B)

Question

A是不同元素的序列，B是A的子序列，A-B是A中的所有元素，但不是B中的所有元素距离(A) = 总和|a(i)-a(i+1)|从 i=1 到 n-1找到一个子序列 B 使得 Dist(B)+Dist(A-B) 最小我知道这可以使用动态规划来解决，但无法弄清楚如何......谁有答案？？？

Answer 1

让我们一次添加一个元素，让我们标记 B 和 A-B，这样最后添加的元素在 B 中。如果我们在 A 中添加 N 个元素，我们需要跟踪 N 个集合 B_i，使得 B_i 是最小的成本解决方案，其中 A-B 中的最后一个元素是 a_i(集合 B_0 是集合 A，因此 A-B 为空)。当我们添加 a_n 时，我们通过添加 |a_n + a_{n-1}| 来更新每个 B_i 的成本。设 B_{n-1} 为集合 (A - B_k) + {a_n}，其中 k 是具有最小值 |a_n - a_k|。