LeetCode 热题100（十五）【动态规划】（3）
15.7最长递增子序列（中等）
给你一个整数数组
nums，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，
[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列
。示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：
输入：nums = [0,1,0,3,2,3] 输出：4示例 3：
输入：nums = [7,7,7,7,7,7,7] 输出：1
思路：
1.dp[i]表示以nums[i]结尾的最长递增子序列的长度，其长度最小为1，因此对dp全部初始化为1
2.当nums[i] > nums[j]时，dp[i] = dp[j] + 1
当nums[i] <= nums[j]时，dp[i]则不变
因此，对于j∈[0 , i )遍历，dp[i] = max (dp[i] , dp[j] + 1)
3.返回dp中最大的值
举例说明：
无
代码：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
int ans = 1;
vector<int> dp(n, 1);
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
}
if(dp[i] > ans) ans = dp[i];
}
return ans;
}
};15.8乘积最大子数组（中等）
给你一个整数数组
nums，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
思路：
1.由于nums中存在负数，因此用两个vector存储以nums[i]结尾的乘积的最大值和最小值
2.初始化f_max[0] = f_min[0] = nums[0]
3.状态转移方程
f_max[i] = max(max(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i])
f_min[i] = min(min(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i])
4.返回f_max的最大值即可
举例说明：
无
代码：
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
vector<int> f_min(n), f_max(n);
f_max[0] = f_min[0] = nums[0];
int ans = f_max[0];
for (int i = 1; i < n; i++) {
f_max[i] = max(max(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i]);
f_min[i] = min(min(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i]);
ans = max(f_max[i], ans);
}
return ans;
}
};15.9 分割等和子集（中等）
给你一个 只包含正整数 的 非空 数组
nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
思路：
1.nums中的所有元素相加为sum，若sum为奇数，则直接返回false
2.令target=sum/2，dp[j]表示nums的子集中的元素之和是否可以等于j
vector<bool> dp(target + 1, false)
初始化dp[0] = true
3.对于nums[i]
dp[j] = dp[j] || dp[j - nums[i]]，其中j∈[ nums[i], target ]
4.返回dp[target]
举例说明：
无
代码：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int i = 0; i < nums.size(); i++){
sum += nums[i];
}
if(sum % 2 == 1) return false;
int target = sum / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for(int i = 0; i < nums.size(); i++){
for(int j = target; j >= nums[i]; j--){
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[target];
}
};15.10最长有效括号（困难）
给你一个只包含
'('和')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"示例 3：
输入：s = "" 输出：0
思路：
1.dp[i]表示以s[i]结尾的最长有效括号数量
2.当s[i]==')',s[i - 1]=='('时，dp[i]=dp[i - 2] + 2;
当s[i]==')',s[i - 1]==')'时，如果s[i - 1 - dp[i - 1]]=='('，dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]
3.返回dp中的最大值
举例说明：
无
代码：
class Solution {
public:
int longestValidParentheses(string s) {
//1.当s[i]==')',s[i - 1]=='('时
//dp[i]=dp[i - 2] + 2;
//2.当s[i]==')',s[i - 1]==')'时
//如果s[i - 1 - dp[i - 1]]=='('
//dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]
int ans = 0;
int n = s.size();
vector<int> dp(n, 0);
for (int i = 1; i < n; i++) {
if (s[i] == ')') {
if (s[i - 1] == '(') dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
else if (i - dp[i - 1] > 0 && s[i - 1 - dp[i - 1]]=='(') {
dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] >= 2) ? dp[i - 2 - dp[i - 1]] : 0);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};原文地址：https://blog.csdn.net/jrrz0828/article/details/143716169
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！