公积金网站建设方案,网站建设的教材,蓬莱网站建设价格,承德网站建设步骤前言
暂时没啥好说的#xff0c;直接进入正题吧
引入
涂色PAINT 读题发现要求的是使一段区间满足要求的最小操作次数#xff0c;考虑用动态规划去做。 第一步#xff1a;考虑缩小规模#xff0c;这里的规模其实就是区间长度#xff0c;那么dp数组应该可以表示某个区间直接进入正题吧
引入
涂色PAINT 读题发现要求的是使一段区间满足要求的最小操作次数考虑用动态规划去做。 第一步考虑缩小规模这里的规模其实就是区间长度那么dp数组应该可以表示某个区间所以到这里dp数组至少是二维的也就是dp[i][j]表示让区间[i,j]合法的最小操作次数。 第二步考虑限制这里暂时看不出来有啥限制那就先不管。 第三步根据写出来的dp数组推转移方程dp[i][j]可以从三个地方转移dp[i-1][j]dp[i][j-1]dp[i-1][j-1]考虑这三个转移有什么特点假设我现在已经求出了dp[i-1][j-1]的染色次数那么当s[i]s[j]时我只需要在对dp[i-1][j-1]染色之前把区间[i,j]进行一次涂色涂成s[i]的颜色这样再执行dp[i-1][j-1]得到的就是对区间[i,j]染成了要求的颜色那么染色次数dp[i][j]dp[i-1][j-1]1;假设我现在已经求出了dp[i-1][j]的染色次数那么当s[i]s[j]时我只需要在对第j个木板进行染色时同时捎带着把第i个木板染了就行那么染色次数dp[i][j]dp[i-1][j];假设我现在已经求出了dp[i][j-1]的染色次数那么当s[i]s[j]时我只需要在对第i个木板进行染色时同时捎带着把第j个木板染了就行那么染色次数dp[i][j]dp[i][j-1];可以考虑三者取最小值。 综上当s[i]s[j]时dp[i][j]min(dp[i-1][j-1]1,dp[i][j-1],dp[i-1][j]) 那么当s[i]!s[j]时没有办法直接求这个大区间那么就从小区间考虑即断开区间。假设断点是k分别求dp[i][k]和dp[k1][j]再加起来即可对于不同的断点取最小值。 第四步考虑要写代码了这里要注意一下dp数组如何初始化我们可以明确的知道区间长度为1时所需要的操作次数就是1所以初始化区间长度为1的值。我们要求的是最小值其它位置上的值可以初始化为一个较大的值也可以直接是0但是在求解过程中要特判一下。 第五步考虑区间dp的板子区间dp一般三层for循环第一层遍历区间长度一般由2开始。 第二层遍历区间左端点根据区间左端点和区间长度区间右端点也就出来了。 第三层遍历区间断点。 这道题目就分析完了还是给了两个版本的代码一个是我初学时写的一个是现在写的都能AC但是现在写的更规范一点
package java动态规划;import java.util.Arrays;
import java.util.Scanner;public class ok涂色 {
public static void main(String[] args) {Scanner scanner new Scanner(System.in);char s[] ( scanner.next()).toCharArray();int n s.length-1;int dp[][] new int[n1][n1];for(int i 0;i n;i) Arrays.fill(dp[i], Integer.MAX_VALUE/2);for(int i 0;i n;i) dp[i][i] 1;for(int len 2;len n;len) {for(int l 1;llen-1n;l) {int r lenl-1;if(s[l]s[r]) dp[l][r] Math.min(dp[l1][r], dp[l][r-1]);else {for(int k l;k r;k)dp[l][r] Math.min(dp[l][r], dp[l][k]dp[k1][r]);}}}System.out.println(dp[1][n]);
}
}import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);String string scanner.next();char[] s string.toCharArray();int[][] dp new int[string.length()][string.length()];// 初始化for (int i 0; i dp.length; i) {dp[i][i] 1;}for (int i 1; i string.length(); i) {for (int j 0; j i string.length(); j) {int l j;int r j i;if (s[l] s[r]) {dp[l][r] Math.min(dp[l 1][r], dp[l][r - 1]);} else {for (int k l; k r; k) {if (dp[l][r] ! 0) {dp[l][r] Math.min(dp[l][k] dp[k 1][r], dp[l][r]);} else {dp[l][r] dp[l][k] dp[k 1][r];}}}}}System.out.println(dp[0][string.length() - 1]);}
}例题2
合并回文子串 这道题稍微难一点关键在于要想到用区间dp去做并且明确区间是谁。我们要合并字符串A和B那么可以考虑一点一点的合并比如A的某个区间和B的某个区间进行合并。 第一步考虑规模这里的规模就是要合并的两个字符串那么其实也就是有两个区间字符串A的区间和字符串B的区间那么dp数组就是四维的dp[i][j][k][l]表示将字符串Ai-Aj与字符串Bk-Bl是否能形成回文串如果可以那么回文串的长度就是j-i1l-k1. 第二步考虑限制限制就是不能更改原串字符的相对顺序但是这里不知道怎么加在dp数组中暂时一放。 第三步推状态转移方程 对于dp[i][j][k][l]考虑一下如果怎么变成回文i和j可以是对应的回文j和k也可以是对应的回文i和l可以是对应的回文k和l可以是对应的回文。 那么考虑i和k可以是对应的回文吗若可以那么位置k必然是在l的右边这样就打乱了数组B的原始顺序所以是不可以的其它非法方案也是类似。 若A[i]A[j]则dp[i][j][k][l]可以从dp[i-1][j-1][k][l]转移过来我只是想判断这种情况是否是回文若是则为1否则则为0所以转移的时候可以直接用或运算转移即dp[i][j][k][l]|dp[i-1][j-1][k][l]。其他情况类似于是有这样的转移方程 若A[i]A[j]则dp[i][j][k][l]|dp[i1][j-1][k][l] 若A[j]A[k]则dp[i][j][k][l]|dp[i][j][k1][l-1] 若A[i]A[l]则dp[i][j][k][l]|dp[i1][j][k][l-1] 若A[k]A[j]则dp[i][j][k][l]|dp[i][j1][k-1][l] 当相等的情况不满足时其实也就是无法构成回文不必考虑。 第四步考虑写代码这里有两个区间所以前两个for循环分别表示两个区间的长度后两个for循环分别表示区间的左端点因为这里没有断开区间操作所以不用遍历断点。这里在写的时候注意是从区间长度为0开始遍历的当总区间长度小于等于1时必然是回文也就是len1len21时直接是dp[i][j][k][l]1。当然也可以预处理出来总长度为1的情况但是不要漏处理了。
参考代码
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int t scanner.nextInt();while (t 0) {t--;String a scanner.next();String b scanner.next();int n1 a.length();int n2 b.length();int dp[][][][] new int[n1 5][n1 5][n2 5][n2 5];a a ;b b ;int res 0;for (int len1 0; len1 n1 1 ; len1) {for (int len2 0; len2 n2 1; len2) {for (int l1 1, r1 len1 l1 - 1; r1 n1 1; l1, r1) {for (int l2 1, r2 len2 l2 - 1; r2 n2 1; l2, r2) {
// int r1 len1l1-1;
// int r2 len2l2-1;if (len1 len2 1) {dp[l1][r1][l2][r2] 1;} else {if (r2 0 a.charAt(l1) b.charAt(r2))dp[l1][r1][l2][r2] | dp[l1 1][r1][l2][r2 - 1];if (r1 0 a.charAt(r1) b.charAt(l2))dp[l1][r1][l2][r2] | dp[l1][r1 - 1][l2 1][r2];if (r1 0 a.charAt(l1) a.charAt(r1))dp[l1][r1][l2][r2] | dp[l1 1][r1 - 1][l2][r2];if (r2 0 b.charAt(l2) b.charAt(r2))dp[l1][r1][l2][r2] | dp[l1][r1][l2 1][r2 - 1];if (dp[l1][r1][l2][r2] 1) {res Math.max(res, len1 len2);}}}}}}System.out.println(res);}}
}
