algorithm - 选择策略的动态规划

Question

假设有两个数组:

a[] = a_1, a_2, ..., a_n
b[] = b_1, b_2, ..., b_m

还有一组s包含 (a_i, b_j)对，在这个集合中，我们需要找到没有两对的最大对数(a_i, b_j)和 (a_i', b_j')满足 i'<i && j'<j .

所以，(a_2, b_1) , (a_3, b_2) (a_1, b_2) 时不允许一起选择和 (a_2, b_1) , (a_1, b_2)和 (a_3, b_2)很好。

例如集合为{(a_1, b_1), (a_1, b_2), (a_2, b_1), (a_3, b_2)} 我们需要选择(a_1, b_1), (a_1, b_2), (a_2, b_1)用于选择 3 对。

看来需要建立一个dp算法对吧？你有什么提示吗？谢谢

Answer 1

我认为这个问题可以简化为longest increasing subsequence通过按 i 递减来排序 a_i 并按 j 递增来排序 b_j(在 i 相等的情况下)。这将给出复杂度为 O(NlogN) 的解决方案，其中 N 是集合中的条目数。

示例:{(a_1, b_1), (a_1, b_2), (a_2, b_1), (a_3, b_2)}

有序:{(a_3, b_2), (a_2, b_1), (a_1, b_1), (a_1, b_2)}

j 的最长递增子序列:{b_1, b_1, b_2}，条目位于索引 {1, 2, 3}

解决方案:{(a_2, b_1), (a_1, b_1), (a_1, b_2)}