class077 区间dp-下【算法】
算法讲解077【必备】区间dp-下
code1 括号区间匹配
// 完成配对需要的最少字符数量
// 给定一个由’[‘、’]‘、’(‘，’)‘组成的字符串
// 请问最少插入多少个括号就能使这个字符串的所有括号正确配对
// 例如当前串是 “([[])”，那么插入一个’]'即可满足
// 输出最少需要插入多少个字符
// 测试链接 : https://www.nowcoder.com/practice/e391767d80d942d29e6095a935a5b96b
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
dp[L][R]
1)L位置和R位置匹配，dp[L+1][R-1]
2)枚举m dp[L][m]+dp[m+1][R]
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;
}
}
code2 664. 奇怪的打印机
// 涂色 & 奇怪打印机
// 假设你有一条长度为5的木板，初始时没有涂过任何颜色
// 你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红
// 用一个长度为5的字符串表示这个目标：RGBGR
// 每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色
// 例如第一次把木板涂成RRRRR
// 第二次涂成RGGGR
// 第三次涂成RGBGR，达到目标
// 返回尽量少的涂色次数
// 测试链接 : https://www.luogu.com.cn/problem/P4170
// 测试链接 : https://leetcode.cn/problems/strange-printer/
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
dp[L][R]:L…R刷出给定的颜色至少涂几次
1)[L]==[R]: dp[L][R-1]或dp[L+1][R]
2)[L]!=[R]：枚举m，dp[L][m]+dp[m+1][R]
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];
}
}
code3 P3205 [HNOI2010] 合唱队
// 合唱队
// 具体描述情打开链接查看
// 测试链接 : https://www.luogu.com.cn/problem/P3205
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过
dp[L][R]
[0]：表示[L]最后插入；[1]：表示[R]最后插入
dp[L][R][0]：以下之和
[L]<[L+1]?dp[L+1][R][0]:0
[L]<[R]?dp[L][R-1][1]:0
dp[L][R][1]：以下之和
[R]>[L+1]?dp[L][R-1][0]:0
[R]>[R-1]?dp[L][R-1][1]:0
返回dp[0][n-1][0]+dp[0][n-1][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;
}
}
code4 546. 移除盒子
// 移除盒子
// 给出一些不同颜色的盒子boxes，盒子的颜色由不同的正数表示
// 你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止
// 每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1）
// 这样一轮之后你将得到 k * k 个积分
// 返回你能获得的最大积分总和
// 测试链接 : https://leetcode.cn/problems/remove-boxes/
boxes[l…r]范围上要去消除，前面跟着k个连续的和boxes[l]颜色一样的盒子
这种情况下，返回最大得分
int f(int[] boxes, int l, int r, int k)
1）前缀先消，尽量长
2）前缀跟后，枚举情况
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;
}
}
code5 1000. 合并石头的最低成本
// 合并石头的最低成本
// 有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头
// 每次 移动 需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数
// 返回把所有石头合并成一堆的最低成本
// 如果无法合并成一堆返回-1
// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-merge-stones/
(n-1)%(k-1)==0，才能合成1份
前1+(k-1)*z个合成1份
后面合成k-1份
最终k个合成1份
枚举z
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];
}
}
code6 730. 统计不同回文子序列
// 统计不同回文子序列
// 给你一个字符串s，返回s中不同的非空回文子序列个数
// 由于答案可能很大，请你将答案对10^9+7取余后返回
// 测试链接 : https://leetcode.cn/problems/count-different-palindromic-subsequences/
dp[i][j]：i…j有多少个不同的回文子序列
1）s[i]!=s[j]：dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]
2）s[i]==s[j]：
a：i…j中内部无a：dp[i+1][j-1]*2+2 ,*2是因为内部的回文子序列首尾添a依然是回文序列，+2是有a aa两个回文子序列
b：i…j中内部有1个a：dp[i+1][j-1]*2+1，+1是内部计算了a回文子序列
c：i…j中内部有不只1个a：dp[i+1][j-1]*2-dp[l+1][r-1]，l是i右边最近的a位置，r是j左边最近的a位置，
因为[l+1,r-1]已经被(l,r)包过一次,所以不需要(i,j)再包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];
}
}
2023-11-22 21:49:27
