力扣爆刷第100天之hot100五連刷86-90

一、139. 單詞拆分

題目鏈接：https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-100-liked
思路：定義dp[i]表示字符串s[0, i]可以被拼接出，那么如果要推導(dǎo)出當(dāng)前s[0,i]可以被拼出，只需要，s[0, i-word.length]可以被拼出，且s[i-word.length] == w，即可推出，此即為遞推公式。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length() + 1];dp[0] = true;for(int i = 1; i < dp.length; i++) {for(String word : wordDict) {if(i < word.length() || dp[i] || !dp[i-word.length()]) continue;dp[i] = isTrue(s, word, i);}}return dp[s.length()];}boolean isTrue(String s, String word, int index) {int i = index - word.length(), j = 0;while(i < index) {if(s.charAt(i) != word.charAt(j)) return false;i++;j++;}return true;}
}

二、300. 最長遞增子序列

題目鏈接：https://leetcode.cn/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-100-liked
思路：定義dp[i]表示區(qū)間[0, i]以nums[i]為結(jié)尾的最長遞增子序列的長度，那么如果nums[i] > nums[j]，故 dp[i] = Math.max(dp[i], dp[j]+1);

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp, 1);int max = 1;for(int i = 1; i < nums.length; i++) {for(int j = 0; j < i; j++) {if(nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j]+1);}}max = Math.max(max, dp[i]);}return max;}
}

三、152. 乘積最大子數(shù)組

題目鏈接：https://leetcode.cn/problems/maximum-product-subarray/description/?envType=study-plan-v2&envId=top-100-liked
思路：求最長乘積子數(shù)組，由于元素有負(fù)數(shù)存在，我們求每一個位置的最大值，該最大值的并不一定依賴的是前一個位置的最大值，也可能是前一個位置的最小值，所以要用兩個數(shù)組記錄分表記錄最大和最小值，在求最大值的時候，dp[i] = max(前一個位置的最大值 * 當(dāng)前元素 ， 當(dāng)前元素， 前一個位置的最小值 * 當(dāng)前元素)。每一個dp[i]由三種裝填推出。

class Solution {public int maxProduct(int[] nums) {int[] dpMax = new int[nums.length];int[] dpMin = new int[nums.length];dpMax[0] = nums[0];dpMin[0] = nums[0];int max = nums[0];for(int i = 1; i < nums.length; i++) {dpMax[i] = Math.max(dpMax[i-1] * nums[i], Math.max(nums[i], dpMin[i-1] * nums[i]));dpMin[i] = Math.min(dpMin[i-1] * nums[i], Math.min(nums[i], dpMax[i-1] * nums[i]));            }for(int i = 1; i < nums.length; i++) {max = Math.max(max, dpMax[i]);}return max;}
}

四、416. 分割等和子集

題目鏈接：https://leetcode.cn/problems/partition-equal-subset-sum/description/?envType=study-plan-v2&envId=top-100-liked
思路：劃分等和子集是背包題的一種變體，只要總和不是奇數(shù)就可以劃分，然后把和的一般作為背包容量，然后物品在外，背包在內(nèi)，背包逆序。

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for(int v : nums) sum += v;if(sum % 2 == 1) return false;sum = sum / 2;int[] dp = new int[sum+1];for(int i = 0; i < nums.length; i++) {for(int j = sum; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);}}return dp[sum] == sum;}
}

五、32. 最長有效括號

題目鏈接：https://leetcode.cn/problems/longest-valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked
思路：使用動態(tài)規(guī)劃做時間超了，可以使用棧做。

class Solution {public int longestValidParentheses(String s) {if(s.length() == 0) return 0;int[] dp = new int[s.length()];int max = 0;for(int i = 1; i < s.length(); i++) {for(int j = 0; j < i; j++) {if(isTrue(s, j, i)) {dp[i] = i-j+1;break;}}max = Math.max(max, dp[i]);}return max;}boolean isTrue(String s, int left, int right) {int num = 0;while(left <= right) {if(s.charAt(left++) == '(') {num++;}else{num--;}if(num < 0) return false;}return num == 0;}
}

使用棧：

class Solution {public int longestValidParentheses(String s) {int maxans = 0;int[] dp = new int[s.length()];for (int i = 1; i < s.length(); 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;}maxans = Math.max(maxans, dp[i]);}}return maxans;}
}