LeetCode 热题100之动态规划2
1.单词拆分
思路分析：动规五部曲
-
dp[i]:表示长度为i的字符串是否能被字典中的单词组成，其状态为dp[i];
-
递推公式：
- 对于每个位置 i（1 到 s.size()），我们需要检查从 j 到 i-1 的子串 s[j…i-1] 是否在字典 wordDict 中，且前缀 s[0…j-1] 已经可以由字典中的单词拆分出来（即 dp[j] == true）。
- 如果满足这些条件，则 dp[i] 可以被标记为 true，表示 s[0…i-1] 可以由字典中的单词拆分出来。
- 递推公式为：dp[i] = dp[j] && (s.substr(j, i-j) in wordSet)
-
初始化：
- dp[0] = true，完全是为了递推公式的进行，其实没有实际含义u（本题来说）
- 其余的dp[i]都初始化为false，表示默认情况下，字符串的前缀不能由字典中的单词拆分出来。
-
遍历顺序：可以看作背包问题，所以先遍历背包，再遍历物品
- 外层循环遍历字符串 s 的每个位置 i，从 i = 1 到 i = s.size()，表示当前我们考虑字符串 s[0…i-1]。
- 内层循环遍历每个可能的子串 s[j…i-1]，从 j = 0 到 j = i-1，检查从 j 到 i-1 的子串是否在字典中，并且前缀 s[0…j-1] 是否可以被拆分。
- 内层循环遍历每个可能的子串 s[j…i-1]，从 j = 0 到 j = i-1，检查从 j 到 i-1 的子串是否在字典中，并且前缀 s[0…j-1] 是否可以被拆分。
-
打印dp数组：
- dp 数组在整个过程中会逐步更新，最终我们关心的是 dp[s.size()] 的值。dp[s.size()] 表示整个字符串 s 是否能被字典中的单词拆分。
- 如果 dp[s.size()] == true，则返回 true，表示字符串 s 可以由字典中的单词组成；否则返回 false，表示无法组成。
具体实现代码（详解版）：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
// 将字典转换为unordered_set以便快速查找
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
// dp[i] 表示 s[0...i-1] 是否能由字典中的单词组成
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
// 遍历字符串的每一个位置
for (int i = 1; i <= s.size(); i++) {
// 遍历子串 s[j...i-1]
for (int j = 0; j < i; j++) {
// 判断 s[j...i-1] 是否在字典中，并且 s[0...j-1] 能拆分
string word = s.substr(j, i - j);
if (wordSet.find(word) != wordSet.end() && dp[j]) {
dp[i] = true;
}
}
}
// 返回 dp[s.size()]，即 s 是否能完全拆分
return dp[s.size()];
}
};
- 时间复杂度： O ( n 2 ) O(n^2) O(n2)
- 空间复杂度： O ( n ) O(n) O(n)
2.最长递增子序列
思路分析：动规五部曲
- dp数组定义：dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度
- 例如，对于数组 nums = [10, 9, 2, 5, 3, 7, 101, 18]，dp[i] 存储的是以 nums[i] 结尾的递增子序列的最长长度。
- 最终，我们的目标是找到数组中任意位置的 dp[i] 的最大值，表示整个数组的最长递增子序列。
- 递推公式：
- 对于每个元素 nums[i]，我们需要遍历它之前的所有元素 nums[j]（j < i），判断是否能够将 nums[i] 追加到 nums[j] 形成一个更长的递增子序列。如果满足 nums[i] > nums[j]，那么就更新 dp[i] 的值：dp[i] = max(dp[i], dp[j] + 1);
- 这里的含义是：如果 nums[i] 比 nums[j] 大，那么 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面形成一个新的递增子序列，dp[i] 就是 dp[j] + 1 的最大值。
- 初始化方式
- 初始化 dp 数组时，每个位置的值都设为 1，因为每个元素至少能构成一个长度为 1 的递增子序列（即该元素本身）。
- 初始时，dp[0] = 1，表示以第一个元素为结尾的最长递增子序列长度为 1
- 遍历顺序
- 外层循环遍历 i，从 i = 1 到 n - 1，表示当前我们考虑的元素是 nums[i]，即以 nums[i] 为结尾的递增子序列。
- 内层循环遍历 j，从 j = 0 到 i - 1，表示考虑 nums[i] 是否可以加到 nums[j] 后形成更长的递增子序列。
- 如果 nums[i] > nums[j]，我们就可以更新 dp[i]。
- 打印dp数组
- 在循环的过程中，dp[i] 会被逐渐更新，最终我们关心的是 dp 数组中的最大值，不是想当然的dp[n - 1],（因为最长的不一定就是以最后一个元素结尾的）它表示整个数组的最长递增子序列的长度。最终返回的 res 就是 dp 数组中的最大值，即最长递增子序列的长度。
具体实现代码（详解版）：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
int res = 1; // 存储最终的结果，初始为1，表示最小的递增子序列长度
// dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
vector<int> dp(n + 1, 1); // 初始化 dp 数组为 1
for (int i = 1; i < n; i++) { // 外层循环遍历每个元素
for (int j = 0; j < i; j++) { // 内层循环遍历元素 nums[i] 之前的所有元素
if (nums[i] > nums[j]) { // 如果 nums[i] > nums[j]，说明可以扩展
dp[i] = max(dp[i], dp[j] + 1); // 更新 dp[i]，取最大值
}
}
res = max(res, dp[i]); // 更新结果，取所有 dp[i] 中的最大值
}
return res; // 返回最长递增子序列的长度
}
};
- 时间复杂度： O ( n 2 ) O(n^2) O(n2)
- 空间复杂度： O ( n ) O(n) O(n)
3.乘积最大子数组
思路分析：动规五部曲
- dp数组定义：
- dp_max[i]：表示以 nums[i] 结尾的子数组的最大乘积。
- dp_min[i]：表示以 nums[i] 结尾的子数组的最小乘积。
- 递推公式
- 对于每个元素 nums[i]，它的最大乘积 dp_max[i] 和最小乘积 dp_min[i] 可以通过以下方式得到：
- 当前元素 nums[i] 本身；
- 当前元素与前一个子数组的最大乘积 dp_max[i-1] * nums[i]；
- 当前元素与前一个子数组的最小乘积 dp_min[i-1] * nums[i]。
- dp_max[i] = max(nums[i], dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i]);
dp_min[i] = min(nums[i], dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i]); - 这里需要注意的是，负数的处理。对于负数，如果 dp_max[i-1] 是正数，乘上负数可能会得到负值，因此我们交换 dp_max[i-1] 和 dp_min[i-1] 的值，保证最大乘积和最小乘积正确更新。
- 对于每个元素 nums[i]，它的最大乘积 dp_max[i] 和最小乘积 dp_min[i] 可以通过以下方式得到：
- 初始化方式：
- dp_max[0] = nums[0] 和 dp_min[0] = nums[0]，即从第一个元素开始，最大和最小乘积就是该元素本身。
- 遍历方式：
- 从 i = 1 开始遍历数组，更新每个位置的最大和最小乘积。
- 打印dp数组：
- 返回最大值即可。res = max(res,dp_max[i]);
具体实现代码（详解版）：
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
// 定义两个dp数组，dp_max和dp_min分别记录当前位置的最大乘积和最小乘积
vector<int> dp_max(n, 0);
vector<int> dp_min(n, 0);
// 初始化第一个元素
dp_max[0] = nums[0];
dp_min[0] = nums[0];
int res = nums[0]; // 记录最大乘积
// 从第二个元素开始遍历
for (int i = 1; i < n; ++i) {
// 如果当前元素为负数，则交换最大和最小乘积
if (nums[i] < 0) {
swap(dp_max[i - 1], dp_min[i - 1]);
}
// 更新最大最小乘积
dp_max[i] = max(nums[i], dp_max[i - 1] * nums[i]);
dp_min[i] = min(nums[i], dp_min[i - 1] * nums[i]);
// 更新最终结果
res = max(res, dp_max[i]);
}
return res;
}
};
可以注意到 dp_max[i] 和 dp_min[i] 只与前一个元素 dp_max[i-1] 和 dp_min[i-1] 有关。因此，可以将空间复杂度优化为 O(1)，只使用常量的空间来存储前一个元素的最大和最小乘积。
具体实现代码（详解版）：
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
// 用来记录前一个位置的最大和最小乘积
int dp_max = nums[0], dp_min = nums[0];
int res = nums[0]; // 记录最大乘积
for (int i = 1; i < n; ++i) {
if (nums[i] < 0) {
swap(dp_max, dp_min); // 如果当前元素为负数，交换最大和最小乘积
}
// 更新当前的最大和最小乘积
dp_max = max(nums[i], dp_max * nums[i]);
dp_min = min(nums[i], dp_min * nums[i]);
// 更新结果
res = max(res, dp_max);
}
return res;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
4.分割等和子集
思路分析：这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。要明确本题中我们要使用的是01背包，因为元素我们只能用一次。
- dp数组的定义：dp[j] 表示： 容量为j的背包，所背的物品价值最大可以为dp[j]。本题中每一个元素的数值既是重量，也是价值。
- 递推公式：相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); - 初始化
- 从dp[j]的定义来看，首先dp[0]一定是0。
- 本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。
- 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200；总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了。所以vector dp(10001, 0);
- 遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！保证物品不重复使用
- 举例推导dp数组
- 如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。
具体实现代码（详解版）：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
// 计算数组中所有元素的总和
for(int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
// 如果总和是奇数，不可能将其分割成相等的两个子集，直接返回 false
if (sum % 2) return false;
// 初始化 dp 数组，dp[j] 表示是否可以得到和为 j 的子集
vector<int> dp(10001, 0);
// 初始化 dp[0] = 0，表示子集和为 0 是可能的（即为空集）
dp[0] = 0;
// 遍历数组中的每一个数（物品），每次尝试更新 dp 数组
for (int i = 0; i < nums.size(); i++) { // 物品
// 遍历容量从 sum / 2 到 nums[i] 的值，确保每个数只被使用一次（从后往前更新）
for (int j = sum / 2; j >= nums[i]; j--) { // 背包
// 更新 dp[j]，选或不选 nums[i]，取其中的最大值
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
// 如果 dp[sum / 2] 的值等于 sum / 2，则表示可以找到一个子集使其和等于 sum / 2
return dp[sum / 2] == sum / 2;
}
};
5.最长有效括号
这道题很难，浅浅记录一下给的思路
思路分析：动规五部曲
- dp数组定义：dp[i] 表示以索引 i 为结尾的最长有效括号子串的长度。
- 递推公式
- 如果 s[i] == ‘(’：这是一个左括号，不能直接形成有效括号对子串。因此 dp[i] 不需要更新（默认是 0），继续处理下一个字符。
- 如果 s[i] == ‘)’：这是一个右括号，我们需要判断它能否与前面的字符构成一个有效括号对。
- s[i-1] == ‘(’
- 如果 s[i-1] == ‘(’，那么 s[i-1] 和 s[i] 就构成了一个有效括号对子串，即 ()。
- 此时，dp[i] 可以由 dp[i-2] 来推导出来（即：dp[i] = dp[i-2] + 2）。
- dp[i-2] 表示在 i-2 位置之前的最长有效括号子串长度，而 +2 是因为当前 () 这一对括号增加了 2 的长度。
- s[i-1] == ')
- 如果 s[i-1] == ‘)’，我们需要进一步判断是否可以形成一个更长的有效括号子串。例如，s[i] 可能会与前面某个有效括号对子串形成一个新的有效括号对子串。
- 假设 dp[i-1] 是以 i-1 为结尾的有效括号子串的长度。我们首先检查 s[i - dp[i-1] - 1] 是否是 ‘(’，如果是，那么可以通过扩展 dp[i-1] 来得到新的有效括号子串。
- 如果 s[i - dp[i-1] - 1] == ‘(’，那么 dp[i] 就应该更新为：dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]，即：
- dp[i-1] + 2 是当前的 ) 和前面的有效括号对子串 () 合起来形成的新的有效括号子串。
- dp[i - dp[i-1] - 2] 是在 i - dp[i-1] - 2 位置之前的最长有效括号子串（如果有的话）。
- 如果 s[i - dp[i-1] - 1] == ‘(’，那么 dp[i] 就应该更新为：dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]，即：
- s[i-1] == ‘(’
- 初始化:dp 数组大小为 n，初始化为 0。maxLength 用于记录最长有效括号子串的长度。
- 遍历顺序：从左往右一次遍历字符
- 打印dp：最后返回maxLength = max(maxLength, dp[i]);
具体实现代码（详解版）：
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
vector<int> dp(n, 0); // dp[i] 表示以第 i 个字符为结尾的最长有效括号子串的长度
int maxLength = 0; // 记录最大有效括号子串的长度
for (int i = 1; i < n; ++i) {
if (s[i] == ')') {
// 如果当前字符是 ')'
if (i - 1 >= 0 && s[i - 1] == '(') {
// 如果前一个字符是 '('，则构成一个有效的括号对
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
} else if (i - 1 >= 0 && s[i - 1] == ')') {
// 如果前一个字符是 ')'，我们需要判断 dp[i - 1] 的有效性
// 需要检查 s[i - dp[i - 1] - 1] 是否是 '('，如果是，则可以构成一个有效括号对
if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
}
}
// 更新最大长度
maxLength = max(maxLength, dp[i]);
}
}
return maxLength;
}
};
- 时间复杂度：O(n）
- 空间复杂度：O(n)
原文地址：https://blog.csdn.net/qq_43060884/article/details/143680468
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！