class077 区间dp-下【算法】

package class077;
// 完成配对需要的最少字符数量
// 给定一个由'['、']'、'('，')'组成的字符串
// 请问最少插入多少个括号就能使这个字符串的所有括号正确配对
// 例如当前串是 "([[])"，那么插入一个']'即可满足
// 输出最少需要插入多少个字符
// 测试链接 : https://www.nowcoder.com/practice/e391767d80d942d29e6095a935a5b96b
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Code01_MinimumInsertionsToMatch {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    String str = br.readLine();
    out.println(compute(str));
    out.flush();
    out.close();
    br.close();
  }
  // 时间复杂度O(n^3)
  public static int compute(String str) {
    char[] s = str.toCharArray();
    int n = s.length;
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        dp[i][j] = -1;
      }
    }
    return f(s, 0, s.length - 1, dp);
  }
  // 让s[l...r]配对至少需要几个字符
  public static int f(char[] s, int l, int r, int[][] dp) {
    if (l == r) {
      return 1;
    }
    if (l == r - 1) {
      if ((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']')) {
        return 0;
      }
      return 2;
    }
    // l...r字符数量 >= 3
    if (dp[l][r] != -1) {
      return dp[l][r];
    }
    // 可能性1 : [l]、[r]本来就是配对的
    int p1 = Integer.MAX_VALUE;
    if ((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']')) {
      p1 = f(s, l + 1, r - 1, dp);
    }
    // 可能性2 : 基于每个可能的划分点，做左右划分
    int p2 = Integer.MAX_VALUE;
    for (int m = l; m < r; m++) {
      p2 = Math.min(p2, f(s, l, m, dp) + f(s, m + 1, r, dp));
    }
    int ans = Math.min(p1, p2);
    dp[l][r] = ans;
    return ans;
  }
}

package class077;
// 涂色 & 奇怪打印机
// 假设你有一条长度为5的木板，初始时没有涂过任何颜色
// 你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红
// 用一个长度为5的字符串表示这个目标：RGBGR
// 每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色
// 例如第一次把木板涂成RRRRR
// 第二次涂成RGGGR
// 第三次涂成RGBGR，达到目标
// 返回尽量少的涂色次数
// 测试链接 : https://www.luogu.com.cn/problem/P4170
// 测试链接 : https://leetcode.cn/problems/strange-printer/
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Code02_Coloring {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    String str = br.readLine();
    out.println(strangePrinter(str));
    out.flush();
    out.close();
    br.close();
  }
  // 时间复杂度O(n^3)
  // 测试链接 : https://leetcode.cn/problems/strange-printer/
  public static int strangePrinter(String str) {
    char[] s = str.toCharArray();
    int n = s.length;
    int[][] dp = new int[n][n];
    dp[n - 1][n - 1] = 1;
    for (int i = 0; i < n - 1; i++) {
      dp[i][i] = 1;
      dp[i][i + 1] = s[i] == s[i + 1] ? 1 : 2;
    }
    for (int l = n - 3, ans; l >= 0; l--) {
      for (int r = l + 2; r < n; r++) {
        // dp[l][r]
        if (s[l] == s[r]) {
          dp[l][r] = dp[l][r - 1];
          // dp[l][r] = dp[l + 1][r];
        } else {
          ans = Integer.MAX_VALUE;
          for (int m = l; m < r; m++) {
            ans = Math.min(ans, dp[l][m] + dp[m + 1][r]);
          }
          dp[l][r] = ans;
        }
      }
    }
    return dp[0][n - 1];
  }
}

package class077;
// 合唱队
// 具体描述情打开链接查看
// 测试链接 : https://www.luogu.com.cn/problem/P3205
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Code03_HeightAndChoir {
  public static int MAXN = 1001;
  public static int[] nums = new int[MAXN];
  public static int[][] dp = new int[MAXN][2];
  public static int n;
  public static int MOD = 19650827;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      for (int i = 1; i <= n; i++) {
        in.nextToken();
        nums[i] = (int) in.nval;
      }
      if (n == 1) {
        out.println(1);
      } else {
        out.println(compute2());
      }
    }
    out.flush();
    out.close();
    br.close();
  }
  // 时间复杂度O(n^2)
  // 严格位置依赖的动态规划
  public static int compute1() {
    // 人的编号范围 : 1...n
    // dp[l][r][0] : 形成l...r的状况的方法数，同时要求l位置的数字是最后出现的
    // dp[l][r][1] : 形成l...r的状况的方法数，同时要求r位置的数字是最后出现的
    int[][][] dp = new int[n + 1][n + 1][2];
    for (int i = 1; i < n; i++) {
      if (nums[i] < nums[i + 1]) {
        dp[i][i + 1][0] = 1;
        dp[i][i + 1][1] = 1;
      }
    }
    for (int l = n - 2; l >= 1; l--) {
      for (int r = l + 2; r <= n; r++) {
        if (nums[l] < nums[l + 1]) {
          dp[l][r][0] = (dp[l][r][0] + dp[l + 1][r][0]) % MOD;
        }
        if (nums[l] < nums[r]) {
          dp[l][r][0] = (dp[l][r][0] + dp[l + 1][r][1]) % MOD;
        }
        if (nums[r] > nums[l]) {
          dp[l][r][1] = (dp[l][r][1] + dp[l][r - 1][0]) % MOD;
        }
        if (nums[r] > nums[r - 1]) {
          dp[l][r][1] = (dp[l][r][1] + dp[l][r - 1][1]) % MOD;
        }
      }
    }
    return (dp[1][n][0] + dp[1][n][1]) % MOD;
  }
  // 时间复杂度O(n^2)
  // 空间压缩
  public static int compute2() {
    if (nums[n - 1] < nums[n]) {
      dp[n][0] = 1;
      dp[n][1] = 1;
    }
    for (int l = n - 2; l >= 1; l--) {
      if (nums[l] < nums[l + 1]) {
        dp[l + 1][0] = 1;
        dp[l + 1][1] = 1;
      } else {
        dp[l + 1][0] = 0;
        dp[l + 1][1] = 0;
      }
      for (int r = l + 2; r <= n; r++) {
        int a = 0;
        int b = 0;
        if (nums[l] < nums[l + 1]) {
          a = (a + dp[r][0]) % MOD;
        }
        if (nums[l] < nums[r]) {
          a = (a + dp[r][1]) % MOD;
        }
        if (nums[r] > nums[l]) {
          b = (b + dp[r - 1][0]) % MOD;
        }
        if (nums[r] > nums[r - 1]) {
          b = (b + dp[r - 1][1]) % MOD;
        }
        dp[r][0] = a;
        dp[r][1] = b;
      }
    }
    return (dp[n][0] + dp[n][1]) % MOD;
  }
}

package class077;
// 移除盒子
// 给出一些不同颜色的盒子boxes，盒子的颜色由不同的正数表示
// 你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止
// 每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1）
// 这样一轮之后你将得到 k * k 个积分
// 返回你能获得的最大积分总和
// 测试链接 : https://leetcode.cn/problems/remove-boxes/
public class Code04_RemoveBoxes {
  // 时间复杂度O(n^4)
  public static int removeBoxes(int[] boxes) {
    int n = boxes.length;
    int[][][] dp = new int[n][n][n];
    return f(boxes, 0, n - 1, 0, dp);
  }
  // boxes[l....r]范围上要去消除，前面跟着k个连续的和boxes[l]颜色一样的盒子
  // 这种情况下，返回最大得分
  public static int f(int[] boxes, int l, int r, int k, int[][][] dp) {
    if (l > r) {
      return 0;
    }
    // l <= r
    if (dp[l][r][k] > 0) {
      return dp[l][r][k];
    }
    int s = l;
    while (s + 1 <= r && boxes[l] == boxes[s + 1]) {
      s++;
    }
    // boxes[l...s]都是一种颜色，boxes[s+1]就不是同一种颜色了
    // cnt是总前缀数量 : 之前的相同前缀(k个) + l...s这个颜色相同的部分(s-l+1个)
    int cnt = k + s - l + 1;
    // 可能性1 : 前缀先消
    int ans = cnt * cnt + f(boxes, s + 1, r, 0, dp);
    // 可能性2 : 讨论前缀跟着哪个后，一起消掉
    for (int m = s + 2; m <= r; m++) {
      if (boxes[l] == boxes[m] && boxes[m - 1] != boxes[m]) {
        // boxes[l] == boxes[m]是必须条件
        // boxes[m - 1] != boxes[m]是剪枝条件，避免不必要的调用
        ans = Math.max(ans, f(boxes, s + 1, m - 1, 0, dp) + f(boxes, m, r, cnt, dp));
      }
    }
    dp[l][r][k] = ans;
    return ans;
  }
}

package class077;
// 合并石头的最低成本
// 有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头
// 每次 移动 需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数
// 返回把所有石头合并成一堆的最低成本
// 如果无法合并成一堆返回-1
// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-merge-stones/
public class Code05_MinimumCostToMergeStones {
  // 时间复杂度O(n^3)
  // 优化策略来自于观察
  // l.....r最终会变成几份其实是注定的，根本就无法改变
  // 那么也就知道，满足(n - 1) % (k - 1) == 0的情况下，
  // 0....n-1最终一定是1份，也无法改变
  // 如果l.....r最终一定是1份
  // 那么要保证l.....m最终一定是1份，m+1...r最终一定是k-1份
  // 如果l.....r最终一定是p份（p>1）
  // 那么要保证l.....m最终一定是1份，那么m+1...r最终一定是p-1份
  // 怎么保证的？枚举行为中，m += k-1很重要！
  // m每次跳k-1！
  // 如果l.....r最终一定是1份
  // 就一定能保证l.....m最终一定是1份
  // 也一定能保证m+1...r最终一定是k-1份
  // 不要忘了，加上最后合并成1份的代价
  // 如果l.....r最终一定是p份
  // 就一定能保证l.....m最终一定是1份
  // 也一定能保证m+1...r最终一定是p-1份
  // 不用加上最后合并成1份的代价
  public static int mergeStones(int[] stones, int k) {
    int n = stones.length;
    if ((n - 1) % (k - 1) != 0) {
      return -1;
    }
    int[] presum = new int[n + 1];
    // 多补了一个0位置，l...r累加和 : presum[r+1] - presum[l]
    for (int i = 0, j = 1, sum = 0; i < n; i++, j++) {
      sum += stones[i];
      presum[j] = sum;
    }
    // dp[l][r] : l...r范围上的石头，合并到不能再合并（份数是确定的），最小代价是多少
    int[][] dp = new int[n][n];
    for (int l = n - 2, ans; l >= 0; l--) {
      for (int r = l + 1; r < n; r++) {
        ans = Integer.MAX_VALUE;
        for (int m = l; m < r; m += k - 1) {
          ans = Math.min(ans, dp[l][m] + dp[m + 1][r]);
        }
        if ((r - l) % (k - 1) == 0) {
          // 最终一定能划分成一份，那么就再加合并代价
          ans += presum[r + 1] - presum[l];
        }
        dp[l][r] = ans;
      }
    }
    return dp[0][n - 1];
  }
}

package class077;
import java.util.Arrays;
// 统计不同回文子序列
// 给你一个字符串s，返回s中不同的非空回文子序列个数
// 由于答案可能很大，请你将答案对10^9+7取余后返回
// 测试链接 : https://leetcode.cn/problems/count-different-palindromic-subsequences/
public class Code06_CountDifferentPalindromicSubsequences {
  // 时间复杂度O(n^2)
  public static int countPalindromicSubsequences(String str) {
    int mod = 1000000007;
    char[] s = str.toCharArray();
    int n = s.length;
    int[] last = new int[256];
    // left[i] : i位置的左边和s[i]字符相等且最近的位置在哪，不存在就是-1
    int[] left = new int[n];
    Arrays.fill(last, -1);
    for (int i = 0; i < n; i++) {
      left[i] = last[s[i]];
      last[s[i]] = i;
    }
    // right[i] : i位置的右边和s[i]字符相等且最近的位置在哪，不存在就是n
    int[] right = new int[n];
    Arrays.fill(last, n);
    for (int i = n - 1; i >= 0; i--) {
      right[i] = last[s[i]];
      last[s[i]] = i;
    }
    // dp[i][j] : i...j范围上有多少不同的回文子序列
    // 如果i>j，那么认为是无效范围dp[i][j] = 0
    long[][] dp = new long[n][n];
    for (int i = 0; i < n; i++) {
      dp[i][i] = 1;
    }
    for (int i = n - 2, l, r; i >= 0; i--) {
      for (int j = i + 1; j < n; j++) {
        if (s[i] != s[j]) {
          // a ..... b
          // i       j
          // 因为要取模，所以只要发生减操作就+mod，讲解041同余原理
          dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1] + mod;
        } else {
          // s[i] == s[j]
          // a......a
          // i      j
          l = right[i];
          r = left[j];
          if (l > r) {
            // i...j的内部没有s[i]字符
            // a....a
            // i    j
            // (i+1..j-1) + a(i+1..j-1)a + a + aa
            dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
          } else if (l == r) {
            // i...j的内部有一个s[i]字符
            // a.....a......a
            // i     lr     j
            // (i+1..j-1) + a(i+1..j-1)a + aa
            dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
          } else {
            // i...j的内部不只一个s[i]字符
            // a...a....这内部可能还有a但是不重要....a...a
            // i   l                             r   j
            // 因为要取模，所以只要发生减操作就+mod，讲解041同余原理
            dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1] + mod;
          }
        }
        dp[i][j] %= mod;
      }
    }
    return (int) dp[0][n - 1];
  }
}