单词划分
题目
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;}