三道动态规划题-最长的有效括号、组合总和I、组合总和II

我会带着你远行 2023-10-04 19:27 36阅读 0赞

### 三道动态规划题-最长的有效括号、组合总和I、组合总和II ###

#### 文章目录 ####

*   *  三道动态规划题-最长的有效括号、组合总和I、组合总和II
     *   *  一、最长的有效括号
         *  二、组合总和 I
         *  三、组合总和 II

#### 一、最长的有效括号 ####

简单来说，给一个字符串，返回一个最长的有效括号

eg:
    input: "()()()))"
    output: 6
    
    eg:
    input: "(())(("
    output: 4

（1）解法

有效括号大概可以包括三种情况

情况1:

"()()"

并列的括号

这种需要的是监测")“,比如i的位置是”)“，那么i-1的位置如果是”("，就说明这个i位置长度为2，然后去看是否有i-2位置，然后加上i-2位置的数就是结果。因为每一个有括号都是这个操作，所以如果前面出现过右括号，那么一定被标记过最长的括号

情况2:

"(())"

嵌套的括号

有效括号的长度就为：

value(i-1) + (i-value(i-1)-1) == '(' ? 2: 0

就是判断最前面的括号是否可以构成有效的括号

情况3:

"(())()"

嵌套+并列

需要在判断i-1位置为做括号时候，加上左括号左边的那个值

2 + value(i-2)

（2）代码

public static int longestValidParentheses(String s){
        
      char[] chars = s.toCharArray();
      int[] dp = new int[s.length()];
      if ("".equals(s) || s.length() == 1) return 0;
      if (s.length() == 2) return chars[0] == '(' && chars[1] == ')' ? 2: 0;
      dp[0] = 0;
      dp[1] = chars[0] == '(' && chars[1] == ')' ? 2: 0;
      // 最大值为第二个括号的数值
      int max = dp[1];
      for (int i = 2; i < s.length(); i++) {
        
        if (chars[i] == ')'){
        
          // 判断左边是否为"("
          if (chars[i-1] == '('){
        
            dp[i] = dp[i-2] + 2;
          }
          // 为")"，判断嵌套结构
          else if(i - dp[i-1] - 1 >= 0 && chars[i-dp[i-1]-1] == '('){
        
            // 处理嵌套并列结构
            // dp[i-1] + 2 : 嵌套结构
            // (i-dp[i-1]-1 > 0 ? dp[i-dp[i-1]-2]: 0) : 并列结构
            dp[i] = (i-dp[i-1]-1 > 0 ? dp[i-dp[i-1]-2]: 0)+ dp[i-1] + 2;
          }else{
        
            dp[i] = 0;
          }
          max = Math.max(max, dp[i]);
        }
      }
      return max;
    }

#### 二、组合总和 I ####

给定一组数字，不重复，给定一个target，有多少组合使得他们的和为target，数组中的数字可以重复使用

eg:
    input: [2,3,4], 8
    output: [2,2,2,2],[2,2,4],[2,3,3],[4,4]

(1) 解法

设定pos为当前索引， rest为当前还需要的target，那么在每一个pos的时候都有两个选择，

1.选择这个数字

2.不选择这个数字

那么我们就可以调用函数：

f(pos+1, rest)

f(pos, rest - value(pos))

函数有两个终止条件：

1.rest==0；说明已经得到了需要的结果

2.rest<value(pos)的时候，这个数字不可以选择

(2)代码

public static void dfs(int[] arr, int target, List<List<Integer>> ans, List<Integer> combine, int idx){
        
      // backend
      if (idx == arr.length) return;
      if (target == 0) ans.add(new ArrayList<>(combine));
      // 循环
      // 不选择
      dfs(arr, target, ans, combine, idx+1);
      // 选择，但是需要选择之后的数值大于target
      if (target - arr[idx] >= 0){
        
        // 把这个值加入combine
        combine.add(arr[idx]);
        dfs(arr, target - arr[idx], ans, combine, idx);
        combine.remove(combine.size() - 1);
      }
    }

#### 三、组合总和 II ####

给定一组数字，一个target，找出存在的组合使得相加为target，每个数字只能使用一次，而且数组存在重复值

eg: 
    input: [1,2,4,1,2], 5
    output: [1,4],[1,2,2]

（1）解法

和上个题目不同，使用简单的递归+回溯的时候，会存在有重复结果的情况，比如\[3,4\], target = 7，那么，得到的结果就是\[3,4\],\[4,3\]，造成了重复

其实造成重复的结果主要是数据中有重复值，如果有一个方法能把重复的数值变成不重复的，那么就可以解决这个问题了

可以采用类似字典的操作，记录每个数值，并且记录数值出现的次数：

[2,2,4,2,3,5,4]
    -- > 
    [[2,3],[3,1],[4,2],[5,1]]

将数值当作数组的第一个元素，出现的次数当作数组的第二个元素，这样就解决了重复的问题

（2）代码

/**
    * pos: 当前的位置
    * rest: 剩余的目标值
    * frep: 转换后的数组
    */
    public void dfs3(int pos, int rest, List<int[]> frep, List<List<Integer>> ans, List<Integer> combine){
        
      // backend
      if (rest == 0) {
        
        ans.add(new ArrayList<Integer>(combine));
        return;
      }
      if (pos >= frep.size() || rest < frep.get(pos)[0]){
        
        return;
      }
    
      // 两种情况
      // 情况1：不选择
      dfs3(pos+1, rest, frep, ans, combine);
      // 情况2：选择
      // 可以选择多个，这个按照数值的个数，和选择之后不能够超过这个rest为准,最多选择most个
      int most = Math.min(rest / frep.get(pos)[0], frep.get(pos)[1]);
      // 将most个数字添加到combine中
      for (int i = 1; i <= most; i++) {
        
        combine.add(frep.get(pos)[0]);
        dfs3(pos+1, rest - frep.get(pos)[0] * i, frep, ans, combine);
      }
      // 选择下一个
    
      // 全部拿出来
      for (int i = 1; i <= most; i++) {
        
        combine.remove(combine.size() - 1);
      }
    }