力扣100题——动态规划（二）
单词划分
题目
139. 单词拆分 - 力扣（LeetCode）
思路
使用dp数组记录当前下标对应的字符串长度能否被正确划分
确定状态转移方程，当j<i时，d[i] = d[j]&&wordDict.contains(s.substring(j, i))
代码
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}最长递增子序列
题目
300. 最长递增子序列 - 力扣（LeetCode）
思路
- 使用dp数组记录以0到当前下标最长的递增子序列长度
- 对dp数组进行初始化为1，因为每个元素都是一个长度为1单独的递增子序列
- 确定状态转移方程，当j<i时，如果nums[j]>nums[i]，即dp[i]=max(dp[i],dp[j]+1)
- 最终遍历整个dp数组找出最大值
代码
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
dp[0] = 1;
for (int i = 1; i < n; i++) {
for(int j = 0;j < i; j++){
if(nums[j] < nums[i]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int max = Integer.MIN_VALUE;
for(int i = 0; i < n; i++){
max =Math.max(max,dp[i]);
}
return max;
}乘积最大的子数组
题目
152. 乘积最大子数组 - 力扣（LeetCode）
思路
按照常规的动态规划思路来做这题的话
- 用dp数组代表从0到当前下标乘积最大的子数组值
- 确定动态规划方程为dp[i] = max(dp[i-1]*nums[i],nums[i])
- 遍历dp数组找出最大值
但是提交上去错误了，问题在于没有考虑到负数这个因素，如果数组中有负数那么此时最大值和最小值会进行反转。所以我们可以进行下面的优化：
- 动态规划：在每个位置，我们需要根据当前数、之前的最大乘积和最小乘积来更新当前的最大和最小值。
- 滚动数组优化：使用两个变量
maxProduct和minProduct代替数组，节省空间。
代码
原来的代码
public int maxProduct(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
for(int i = 1; i < n; i++){
dp[i] = Math.max(dp[i-1]*nums[i], nums[i]);
}
int max = Integer.MIN_VALUE;
for(int i=0;i<n;i++){
max = Math.max(max,dp[i]);
}
return max;
}优化后的代码
public int maxProduct(int[] nums) {
int n = nums.length;
int min = nums[0];
int max = nums[0];
int result = nums[0];
for(int i=1;i<n;i++){
if(nums[i]<0){
int t = max;
max=min;
min=t;
}
min=Math.min(nums[i],nums[i]*min);
max=Math.max(nums[i],nums[i]*max);
result = Math.max(max,result);
}
return result;
}分割等和子集
题目
416. 分割等和子集 - 力扣（LeetCode）
思路
- 目标：判断是否能将数组划分为两个子集，使得两个子集的和相等。
- 总和为奇数的数组不可能被划分成两个和相等的子集，所以如果数组的总和为奇数，直接返回
false。 - 如果总和为偶数，那么问题就变成了：能否找到一个子集，其和为
sum / 2。 - 动态规划是经典的背包问题思路：我们需要判断是否存在一个子集，其和为
sum / 2。 - 设
dp[i]表示能否找到和为i的子集，那么我们需要更新dp数组。
代码
public boolean canPartition(int[] nums) {
int sum = 0;
Arrays.sort(nums);
for(int num : nums){
sum += num;
}
if(sum%2!=0){
return false;
}
int target = sum/2;
boolean[]dp =new boolean[target+1];
dp[0] = true;
for(int num : nums){
for(int i=target;i>=num;i--){
dp[i] = dp[i]||dp[i-num];
}
}
return dp[target];
}最长有效括号
题目
32. 最长有效括号 - 力扣（LeetCode）
思路
这题目更适合用栈来写，思路和代码都会清晰一点
- 定义一个 dp 数组，其中
dp[i]表示以第i个字符为结尾的最长有效括号子串的长度。 - 如果遇到右括号
')'，我们需要检查它的前一个字符是否是左括号'('或者前一个位置结束的有效括号是否与这个右括号能够匹配。 - 通过维护 dp 数组，可以在遍历字符串的过程中计算出最大值。
代码
public int longestValidParentheses(String s) {
int n = s.length();
int[] dp = new int[n]; // dp[i] 表示以 i 结尾的最长有效括号子串长度
int maxLen = 0;
for (int i = 1; i < n; i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
// 如果前一个是 '('，则直接匹配
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
// 如果前一个是 ')'，且它之前的匹配的括号也是有效的
dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxLen = Math.max(maxLen, dp[i]); // 维护最大值
}
}
return maxLen;
}