三道动态规划题-最长的有效括号、组合总和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

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