LC-单词拆分、最长递增子序列、乘积最大子数组、分割等和子集、最长有效括号

单词拆分

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;
    }
}