题意:给出 n 组数,每组有两个数,第一个数总是比第二个数字小。如果两组数 (a,b) 和 (c,d) 之间,有 b < c,那么就称 (a,b)和 (c,d) 之间形成了一个chain。求出这 n 组数中能形成的最长的 chain 的长度。
例子:输入[[1,2], [2,3], [3,4]]
,因为[1,2] -> [3,4]
,所以返回2。
思路:又是一道动态规划题目。因为第一个数字总是小于第二个数字,所以我们可以先将这些组按第一个数字来排序。然后我们声明一个长度为n 的数组,dp[i]
表示以 pairs[i]
作为 chain 的最后一个元素的情况下,能形成的 chain 的最大长度。于是对于 pairs[i]
,在索引范围在 0~i-1
的所有 pair 中,如果 pairs[j]
满足 pairs[j][1] < pairs[i][0]
,那么 pairs[i]
就可以连到 pairs[j]
上;如果 pairs[j']
是满足条件的 j 中 pairs[j][1]
最大的,那么这样形成的 chain 就是最长的。因此我们可以得到状态转移方程为:dp[i] = {max(dp[i], dp[j]+1), j >= 0 && j < i, pairs[j][0] < pairs[i][0]}
。
在排序时,我们可以使用 std::sort
并传入自定义的比较函数,配合 lambda 语法可以使得排序非常简单。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { if (pairs.size() == 0 || pairs[0].size() < 2) { return 0; } // 将 pairs 按照第一个数字的大小顺序升序排列 std::sort(pairs.begin(), pairs.end(), [](auto &left, auto &right){ return left[0] < right[0]; }); int size = pairs.size(); vector<int> dp(size,1); for (int i = 1; i < size; i++) { for (int j = 0; j < i; j++) { if (pairs[j][1] < pairs[i][0]) { dp[i] = max(dp[i], dp[j] + 1); } } } int len = 0; for (int i = 0; i < size; i++) { if (dp[i] > len) { len = dp[i]; } } return len; } }; |