1.求一个字符串最少修改多少次能变成回文串
只过了30%，用的dp，内存超出了，请问还有更好的做法吗？显示的是字符串长度n<100时的测试数据是30%，n<10000时的测试数据是100%。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String str = in.next();
int[][] dp = new int[n][n];
for (int i = n - 2; i >= 0 ; i--) {
for (int j = i + 1; j < n; j++) {
if(str.charAt(i) == str.charAt(j)){
dp[i][j] = dp[i+1][j-1];
}
else{
dp[i][j] = dp[i+1][j-1] + 1;
}
}
}
System.out.print(dp[0][n-1]);
} 2.一个m*n的方块，种花，每个方块必须有花，每种花的个数必须相等，每个相邻方块的花的种类必须不同，满足这三个条件，求最少的花的种类。 没做。求做法
3.一个数组，求它的连续子数组的或运算取得最大值时，这个连续子数组的长度是多少？
也是用的dp，又是内存超出，只过了50%，菜鸡落泪。
4.没看，图类型的。
全部评论
(5) 回帖