基于动态规划的策略选择：无i'<i且j'<j约束的最大配对数求解

嘿，这个问题其实可以通过转化为最长非递增子序列的动态规划问题来解决，我给你一步步拆解清楚：

首先明确约束：我们选的配对集合中，不能存在任意两个配对(a_i,b_j)和(a_i',b_j')，满足i'<i且j'<j——换句话说，集合里的任意两个配对，不能出现一个在另一个的「左上方」（行号更小，列号也更小）。

同一行的所有配对都可以选（行号相同，不存在i'<i），同一列的所有配对也可以选（列号相同，不存在j'<j）；只有跨行列且左上方的配对才会冲突。

1. 预处理配对序列 #

把集合S中的所有配对按以下规则排序：

• 先按a的索引i从小到大排序（行号升序）
• 对于行号相同的配对，按b的索引j从大到小排序（列号降序）

这样排序的目的是：同一行的配对按列号降序排列，保证它们能全部被纳入最长非递增子序列中（不会因为列号递增而被排除）。

2. 定义动态规划状态 #

提取排序后的配对序列中的j值，得到一个序列J = [j_1, j_2, ..., j_k]（k是S中配对的总数）。

定义dp[i]为：以序列中第i个j值结尾的最长非递增子序列的长度。

3. 状态转移方程 #

对于每个i（从0到k-1）：
dp[i] = 1 + max( dp[0..i-1] 中所有满足 J[j] >= J[i] 的 dp[j] 的值 )
如果没有满足条件的j，那么dp[i] = 1（只包含当前这个配对）。

4. 计算最终结果 #

最终的最大配对数就是dp数组中的最大值。

拿题目中的例子来看：
集合S = {(a1,b1), (a1,b2), (a2,b1), (a3,b2)}
排序后的配对序列是：(a1,b2), (a1,b1), (a2,b1), (a3,b2)
对应的J序列是：[2, 1, 1, 2]

计算dp数组：

• dp[0] = 1（只有j=2）
• dp[1]：J[0] >= J[1]（2>=1），所以dp[1] = dp[0]+1=2
• dp[2]：J[0]>=1，J[1]>=1，取max(dp[0],dp[1])=2，所以dp[2]=2+1=3
• dp[3]：J[0]=2>=2成立，对应dp[0]=1；J[1]、J[2]的j值都小于2，所以max是1，dp[3]=1+1=2

dp数组的最大值是3，正好和题目中的最优结果一致。

上面的基础DP方法时间复杂度是O(k²)，如果配对数量很大，可以用二分优化把时间降到O(k log k)：维护一个数组tails，其中tails[i]表示长度为i+1的最长非递增子序列的最后一个元素的最大值。遍历J序列时，用二分查找找到第一个小于当前J[i]的位置，更新tails数组。

不过题目要求基于动态规划，基础的DP解法已经完全符合要求了。

内容的提问来源于stack exchange，提问作者user8142520