动态规划可以帮助解决这个问题吗？

Question

注意 - 如果您有其他比 DP 效果更好的方法，请提出建议。

我有一个像这样的 2D 列表

[ [1,2], [1,2], [1,3], [5,4], [4,6] ]

。我想将其展平为一维列表，以便没有。结果列表中不同值的数量应该是最小值，如下所示

[1,1,1,4,4]

此外，子数组的长度可以彼此不同。另一个例如。

[ [1,2,3], [1,3], [1,8], [5,6], [6,5], [4] ]

应转换为

[1,1,1,5,5,4]

或

[1,1,1,6,6,4]

。

我觉得 dp/recursion 是解决这个问题的方法，但我很难弄清楚。有人可以指导我吗？

我尝试了一种方法，即根据值在列表中重复的次数来维护值的分数，然后选择列表中分数最高的值，但是当分数相同并且列表就像这样时，这种方法不起作用以下。

[[1, 2],[1, 2],[1, 2],[1, 3],[3, 4],[3, 4],[4, 5, 9]]

这应该转变为

[1,1,1,1,4,4,4]

但我的方法给了我

[1,1,1,1,3,3,4]

Answer 1

这个问题没有已知的“好”算法——这是 NP 完全的“命中集问题”。

但是对于小例子，您可以通过维护迄今为止选择的唯一元素的命中集来进行搜索，并在命中集尚未命中下一组时尝试所有可能性。

类似这样的：

def _smallest(xs, i, used):
    if len(xs) == i:
        return set(used)
    if any(x in used for x in xs[i]):
        return _smallest(xs, i+1, used)
    return min((_smallest(xs, i+1, used|{x}) for x in xs[i]), key=len)

def smallest(xs):
    return _smallest(xs, 0, set())

cases = [
    [[1,2], [1,2], [1,3], [5,4], [4,6]],
    [[1,2,3], [1,3], [1,8], [5,6], [6,5], [4]],
    [[1, 2], [1, 2], [1, 2], [1, 3], [3, 4], [3, 4], [4, 5, 9]],
]
for c in cases:
    s = smallest(c)
    print(c, "->", [next(i for i in x if i in s) for x in c])

注意：通过就地更新

used

集合而不是每次构造新集合，可以提高运行时效率，但代码如上面所示更简单、更短。

输出：

[[1, 2], [1, 2], [1, 3], [5, 4], [4, 6]] -> [1, 1, 1, 4, 4]
[[1, 2, 3], [1, 3], [1, 8], [5, 6], [6, 5], [4]] -> [1, 1, 1, 5, 5, 4]
[[1, 2], [1, 2], [1, 2], [1, 3], [3, 4], [3, 4], [4, 5, 9]] -> [1, 1, 1, 1, 4, 4, 4]