力扣 hot100 -- 动态规划（下）
目录
💻最长递增子序列
AC 动态规划
AC 动态规划(贪心) + 二分
🏠乘积最大子数组
AC 动规
AC 用 0 分割
🐬分割等和子集
AC 二维DP
AC 一维DP
⚾最长有效括号
AC 栈 + 哨兵
💻最长递增子序列
300. 最长递增子序列 - 力扣（LeetCode）
子序列：不用连续
子串：要求连续
AC 动态规划
时间 O(n^2)
/*
dp[i] : 第 i 个元素结尾的最长子序列长度（下标0开始）
dp[i] = max(dp[i], dp[j] + 1)
初始化 : dp[i] = 1
*/
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n + 1, 1);for (int i = 1; i < n; ++i)for (int j = 0; j < i; ++j) if (nums[j] < nums[i])dp[i] = max(dp[i], dp[j] + 1);int ans = 1;for (auto x : dp)ans = max(ans, x);return ans;}
};AC 动态规划(贪心) + 二分
二分实现 O(logn) 查找，为了使用二分，我们需要让 dp[] 数组有序，所以需要改变 dp[] 数组的含义（状态）
贪心策略：tails 中存储的元素越小，上升的子序列越长
举例解释
nums[] = {7, 8, 9, 1, 2, 3, 4, 5};
遍历完 7 8 9 后 tails[] = {7, 8, 9};
接着遍历到 1，那么二分查找 tails[]，找到第一个比 tails 大的位置，即 7，替换后变成
tails[] = {1, 8, 9};
如果没有比当前 nums[] 值大的元素，直接加到后面
最后输出 tails[] 长度，就是最长上升子序列长度
时间 O(nlogn)
/*
tails[i] : 长度 i+1 子序列的尾部元素
1）nums[] 中当前元素 x > tails.back(), x 插入 tails 最后
2）否则, 二分查找 tails[] 中第一个 > x 的元素, 替换成 x
最后返回 tails[] 大小
*/
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> tails;tails.push_back(nums[0]);for (auto x : nums) {if (x > tails.back()) {tails.push_back(x);continue;}int l = 0, r = tails.size() - 1;while (l < r) {int mid = (l + r) >> 1;if (tails[mid] < x)l = mid + 1;elser = mid;}tails[l] = x;}return tails.size();}
};
// 检验二分边界
// tails[]: 1 3 5 -- x: 3/4
// tails[]: 1 3 5 7 -- x: 3/4/5🏠乘积最大子数组
152. 乘积最大子数组 - 力扣（LeetCode）
注意是“连续子数组”
AC 动规
1）滚动
本题，dp[i] 都是基于 dp[i -1] 得到的，所以可以将一维数组变成一个变量，即 “滚动数组”
2）坑
遍历数组，更新 3 个 dp 变量时，maxDp 基于上一个 maxDp 没问题
但是 maxDp 更新后，minDp 还是基于上一个 maxDp
所以需要一个临时变量保存上一个 maxDp
然后 dp 可以直接基于新的 maxDp
3）坑2
题目保证 32 位，也就是 10^9，但是，样例里有一组 10^19 次方的....
所以，有 4 个地方要加 double，防止类型不匹配 或 heap flow（堆溢出）
时间 O(n)
/*
滚动数组，一维数组变变量
maxDp[i] : 第 i 个元素结尾的最大值
minDp[i] : 第 i 个元素结尾的最小值
dp[i] : 只选前 i 的元素的最大值
*/
class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();if (n == 1)return nums[0];double maxDp = nums[0], minDp = nums[0], dp = nums[0];for (int i = 1; i < n; ++i) {double t = maxDp; // 临时变量maxDp = max(max((double)nums[i], maxDp*nums[i]), minDp*nums[i]);minDp = min(min((double)nums[i], t*nums[i]), minDp*nums[i]);dp = max(dp, maxDp); // 上一个 dp 和 新的 maxDp 取较大值}return (double)dp;}
};AC 用 0 分割
用 0 分割成多个连续的子数组，对每个子数组：
1）偶数个负数，直接相乘（负数数量 0, 2, 4, 6...）
2）奇数个负数：
a. 左到右相乘，直到最后一个负数之前
b. 右到左，直到最后一个负数之前
取 a. b. 的 max()
3）实际遍历中，先左到右遍历，后右到左遍历，单次遍历中，只需要动态更新最大值（包含了偶数，奇数个负数的两种情况）
时间 O(n)
class Solution {
public:int maxProduct(vector<int>& nums) {double ans = nums[0];double t = 1; // 临时变量保存乘积// 左到右for (int i = 0; i < nums.size(); ++i) {t *= nums[i];ans = max(ans, t);if (t == 0)t = 1; // 用 0 分割子数组}// 右到左t = 1;for (int i = nums.size() - 1; i >= 0; --i) {t *= nums[i];ans = max(ans, t);if (t == 0)t = 1;}return (int)ans;}
};🐬分割等和子集
416. 分割等和子集 - 力扣（LeetCode）
AC 二维DP
01背包画表格类似这样
坑：
和为奇数，直接返回 false，否则打表会发现，出现了一些奇怪的错误
含义：
dp[i][j] : 只从 [0, i] 区间里选，每个数最多选 1 次，和为 j
递推式：
选第 i 个：dp[i - 1][j - nums[i]]
不选第 i 个：dp[i - 1][j]
第 i 个数 == 总和的一半
dp[i][j] = dp[i - 1][j - nums[i]] || dp[i - 1][j] || (nums[i] == sum/2)
初始化：
根据递推式，只需初始化第 0 行，即只从 [0, 0] 区间选，和为 nums[0] 的 == 1，其他为 0
输出：
dp[n - 1][sum / 2]：表示从 [0, n - 1] 选, 和为总和一半, 即等和子集
O(n * sum/2)
// dp[i][j] = dp[i - 1][j - nums[i]] || dp[i - 1][j] || (nums[i] == sum/2)
// 输出 dp[n - 1][sum / 2]
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0, n = nums.size();for (auto x : nums)sum += x;if (sum % 2 == 1)return false; // 和为奇数// n 行, 每一行就是 vector<int>(), 这一行表示总和 0 ~ sum/2, 初始化为 0vector<vector<int>> dp(n, vector<int>(sum / 2 + 1, 0));if (nums[0] <= sum/2)dp[0][nums[0]] = 1; // 从 [0, 0] 选, 和为nums[0]for (int i = 1; i < n; ++i)for (int j = 0; j <= sum/2; ++j) {dp[i][j] = dp[i - 1][j] || (nums[i] == sum/2);if (j >= nums[i]) // 防止越界dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]];}return dp[n - 1][sum / 2];}
};
AC 一维DP
考虑到递推式 dp[i][j] 都是来源于 dp[i - 1][...]，可以将二维变成一维，优化空间👇
那么为什么要逆序遍历子集的和 j 呢，因为，dp[j] 都是基于上一行的，旧的(未被修改的) dp[j] 和 dp[j - nums[i]]
如果顺序遍历，dp[j - nums[i]] 会被多次修改，也就是取了多个元素，而题目规定只能取一个
顺序遍历适合完全背包，而不是 01 背包
// dp[j] ：和为 j
// dp[j] = dp[j - nums[i]] || dp[j] || (nums[i] == sum/2)
// 输出 dp[sum / 2]
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0, n = nums.size();for (auto x : nums)sum += x;if (sum % 2 == 1)return false; // 和为奇数// 和的一半 +1 个元素vector<int> dp(sum / 2 + 1, 0);if (nums[0] <= sum/2)dp[nums[0]] = 1; // 从 [0, 0] 选, 和为nums[0]for (int i = 1; i < n; ++i)for (int j = sum/2; j >= 0; --j) {dp[j] = dp[j] || (nums[i] == sum/2);if (j >= nums[i]) // 防止越界dp[j] = dp[j] || dp[j - nums[i]];}return dp[sum / 2];}
};
⚾最长有效括号
32. 最长有效括号 - 力扣（LeetCode）
AC 栈 + 哨兵
求连续的最长有效括号
如果不连续，栈就会被清空最后一个元素，再插入新的下标，即更新了栈顶的元素
初始插入 -1（哨兵），防止先遇到右括号，栈为空就 pop 导致的栈溢出
时间 O(n)
class Solution {
public:int longestValidParentheses(string s) {int ans = 0;if (s.size() == 0) return 0;stack<int> st;st.push(-1); // 防止溢出, 为后面的连续准备for (int i = 0; i < s.size(); ++i) {if (s[i] == '(') // 左括号st.push(i); else { // 右括号st.pop();if (st.empty())st.push(i);else ans = max(ans, i - st.top()); // 连续的长度}}return ans;}
};