动态规划专题

leetcode 300. 最长递增子序列

示例：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

代码实现：

方法一：动态规划

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();// 初始化为1，表示从每个位置开始的最长递增子序列的长度至少为1vector<int> dp(n, 1);int res = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nums[i] > nums[j]) {// 到第i个数，可能对应多个不同的递增子序列，// 用max运算保证最终dp[i]是所有子序列中最长的长度dp[i] = max(dp[i], dp[j] + 1);}}}for (int i = 0; i < n; ++i) {res = max(res, dp[i]);}return res;}
};

复杂度分析：

• 时间复杂度：两轮循环，故为 O(n2)O(n^2)O(n2) ；
• 空间复杂度：dp 数组，空间复杂度为 $O(n)$ 。

方法二：patience sorting

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();// 初始时预留n个位置用于放各个牌堆（这n个位置不一定会用完）vector<int> pokerPiles(n, 0);// 初始时，将牌堆数置为0int pileNum = 0;for (int i = 0; i < n; ++i) {// right始终指向下一个空的牌堆int left = 0, right = pileNum;/*** 寻找左侧边界的二分搜索 ***/while (left < right) {int mid = left + (right - left) / 2;if (pokerPiles[mid] < nums[i])left = mid + 1;else right = mid;}// 如果左侧边界指向了下一个空牌堆的位置，让牌堆数加1if (left == pileNum) ++pileNum;// 将当前数字nums[i]放到left索引处pokerPiles[left] = nums[i];}// 最终牌的堆数就是最长递增子序列的长度return pileNum;}
};

复杂度分析：

• 时间复杂度：$O(n\log n)$；
• 空间复杂度：$O(k)$，$k$ 是最长递增子序列的长度，最坏情况下是整个数组的长度，此时空间复杂度退化为 $O(n)$ 。

leetcode 354. 俄罗斯套娃信封问题

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

代码实现：

class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {int n = envelopes.size();// 对envelopes的w按升序排列，h按降序排列sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);});// 接下来再求出h的最长递增子序列即可// 用patience sorting算法vector<int> pokerPiles(n, 0);int pileNum = 0;for (int i = 0; i < n; ++i) {int left = 0, right = pileNum;while (left < right) {int mid = left + (right - left) / 2;if (pokerPiles[mid] < envelopes[i][1]) left = mid + 1;else right = mid;}if (left == pileNum) ++pileNum;pokerPiles[left] = envelopes[i][1];}return pileNum;}
};

复杂度分析：

• 时间复杂度：$O(n\log n)$

leetcode 53. 最大子数组和

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

代码实现：

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();// 一维dpvector<int> dp(n, 0);// base case: 第一个元素前没有子数组dp[0] = nums[0];/*** DP ***/// 因为已经处理了base case，故i从1开始for (int i = 1; i < n; ++i) {// dp数组的含义是: 以nums[i]结尾的“最大子数组和”为dp[i]dp[i] = max(nums[i], nums[i] + dp[i-1]);}int maxSum = INT_MIN;for (int i = 0; i < n; ++i) {maxSum = max(maxSum, dp[i]);}return maxSum;}
};

复杂度分析：

• 时间复杂度：$O(n)$；
• 空间复杂度：$O(n)$。

leetcode 1143. 最长公共子序列

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

代码实现：

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();vector<vector<int>> dp(m+1, vector<int>(n+1, 0));for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (text1[i-1] == text2[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}}return dp[m][n];}
};

复杂度分析：

• 时间复杂度：$O(mn)$，$m$ 和 $n$ 分别是输入的两个字符串的长度；
• 空间复杂度：$O(mn)$，$m$ 和 $n$ 分别是输入的两个字符串的长度。