单词拆分

1. 定义状态：

   • 设 dp[i] 表示字符串 s 的前 i 个字符 s[0:i] 是否可以由 wordDict 中的单词拼接而成。

2. 状态转移方程：

   • 设 wordDict 中的某个单词 word，如果 s[j:i] (即 s 从 j 到 i-1 的子串) 在 wordDict 中，且 dp[j] == true，则 dp[i] = true。 dp[i]=dp[j]且s[j:i]∈wordDictdp[i] = dp[j] \quad \text{且} \quad s[j:i] \in wordDictdp[i]=dp[j]且s[j:i]∈wordDict
   • 其中 j 取值范围为 [0, i)。

3. 初始化：

   • dp[0] = true，表示空字符串可以被成功分解（作为起点）。
   • 其他 dp[i] 初始为 false，表示尚未判断。

4. 目标：

   • 计算 dp[s.length()] 是否为 true，即 s 是否可以由 wordDict 拼接而成。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> wordSet = new HashSet<>(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] && wordSet.contains(s.substring(j,i))){dp[i] = true;break;//找到一个可行的拆分点就可以停止}}}return dp[n];}
}

最长递增子序列

动态规划：

• 使用动态规划的方法可以较为直观地解决这个问题。我们定义一个数组 dp，其中 dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度。
• 状态转移方程：对于每个 nums[i]，我们可以遍历所有之前的元素 nums[j]，如果 nums[i] > nums[j]，则 dp[i] = max(dp[i], dp[j] + 1)。
• 最终的答案就是 dp 数组中的最大值。

时间复杂度是 O(n^2)，其中 n 是数组的长度。

class Solution {public int lengthOfLIS(int[] nums) {if(nums.length == 0){return 0;}int n = nums.length;int[] dp = new int[n];dp[0] = 1;for(int i = 1;i < n;i++){dp[i] = 1;//每个元素至少是一个递增子序列for(int j = 0;j < i;j++){if(nums[i] > nums[j]){dp[i] = Math.max(dp[i],dp[j] + 1);}}}int max = 0;for(int i = 0;i < n;i++){max = Math.max(max,dp[i]);}return max;}
}

乘积最大子数组

1. 动态规划：我们使用动态规划的方法来解决这个问题。由于数组中有负数，可能会影响最大值和最小值，所以我们需要追踪当前位置的最大值和最小值。

   • maxProduct[i] 表示到第 i 个元素为止的子数组的最大乘积。
   • minProduct[i] 表示到第 i 个元素为止的子数组的最小乘积。

   每次更新最大值和最小值时，都要考虑：

   • 当前元素本身 nums[i]
   • 当前元素和之前的最大值 maxProduct[i-1] 乘积
   • 当前元素和之前的最小值 minProduct[i-1] 乘积（负数乘积可能变大）

2. 状态转移：对于每一个元素 nums[i]，我们要更新当前的最大值和最小值：

   • maxProduct[i] = max(nums[i], nums[i] * maxProduct[i-1], nums[i] * minProduct[i-1])
   • minProduct[i] = min(nums[i], nums[i] * maxProduct[i-1], nums[i] * minProduct[i-1])

3. 最终，我们需要返回所有 maxProduct 中的最大值。

class Solution {public int maxProduct(int[] nums) {if(nums == null || nums.length == 0){return 0;}//初始化int maxProd = nums[0];//记录当前的最大乘积int minProd = nums[0];//记录当前的最小乘积int result = nums[0];for(int i = 1;i < nums.length;i++){int tempMax = maxProd;maxProd = Math.max(nums[i],Math.max(nums[i] * maxProd,nums[i] * minProd));minProd = Math.min(nums[i],Math.min(nums[i] * tempMax,nums[i] * minProd));result = Math.max(result,maxProd);}return result;}
}

分割等和子集

1. 问题转化：

   • 如果可以将数组分割成两个子集，使得它们的元素和相等，那么这两个子集的和应该是 sum(nums) / 2。
   • 设 target = sum(nums) / 2，如果 sum(nums) 是奇数，那么直接返回 false，因为无法将奇数均分成两个整数。
   • 如果 sum(nums) 是偶数，问题就变成了：能否在数组中找到一个子集，它的和为 target。

2. 动态规划：

   • 我们可以使用动态规划来判断是否能找到一个和为 target 的子集。可以使用一个布尔型数组 dp，其中 dp[i] 表示是否能从 nums 中找到一个子集，使得该子集的和为 i。
   • 初始状态是 dp[0] = true，表示和为 0 的子集是存在的（即不选任何元素）。
   • 对于每个元素 num，我们从 target 开始倒着更新 dp[i]，使得每次状态转移时不会覆盖前一步的结果。

class Solution {public boolean canPartition(int[] nums) {int sum = 0;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;//和为0的子集是空集for(int num : nums){//从大到小更新dp数组，确保不重复使用同一个元素for(int i = target;i >= num;i--){dp[i] = dp[i] || dp[i - num];}}return dp[target];}
}

最长有效括号

动态规划的方法通过定义一个状态数组 dp 来表示以当前位置为结尾的最长有效括号长度。

1. 定义 dp[i] 为以 i 为结尾的最长有效括号的长度。
2. 遍历字符串，对于每个 )：
   • 如果 s[i] 为 )，则判断 s[i-1] 是否为 (，若是，则构成一个有效括号，dp[i] = dp[i-2] + 2。
   • 如果 s[i-1] 为 )，则判断 s[i - dp[i-1] - 1] 是否为 (，如果是，则组成更长的有效括号，更新 dp[i]。
3. 最终返回 dp 数组中的最大值。

class Solution {public int longestValidParentheses(String s) {int n = s.length();if(n == 0){return 0;}int[] dp = new int[n];int maxLength = 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] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '('){dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] -  2] : 0) + 2;}maxLength = Math.max(maxLength,dp[i]);}       }return maxLength;}
}