蓝桥杯2016年第七届真题-密码脱落（Java代码）

解题思路:参考https://blog.csdn.net/xuzhuang1996/article/details/65935937的这篇博客

注意事项:dp的长度设大一点，因为题目说字符串不大于1000说明可能等于1000

参考代码:

import java.util.Scanner;

public class Main{

static int dp[][] = new int[1000][1000];

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner sc = new Scanner(System.in);

String s = sc.next();

char ch[] = s.toCharArray();

int n = s.length();

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (ch[i] == ch[n - j - 1]) {

dp[i + 1][j + 1] = dp[i][j] + 1;

} else {

dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);

}

}

}

System.out.print(n - dp[n][n]);

}

}