小红书9.12 笔试第二题

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String s = in.nextLine();
                //构建dp数组，dp[i]代表的是前i个字符所能切成的最少字串数量
                //比如： dp[4]代表的就是前4个字符，也就是dp[0]-dp[3]所切割的最少字串数量
		int[] dp = new int[s.length()+1];
		char[] chr = s.toCharArray();
                //前i个字符能切的最大子串数量
                //比如前3个字符最多能切三次
		for (int i = 0; i <= s.length(); ++i) {
			dp[i] = i;
		}
		dp[0] = 0;
                //遍历字符数组
		for (int i = 1;i<=s.length();i++){
                        //从后向前找，找到与当前s[i]相同的字符
			for (int j = s.length(); j >= i; --j) {
                                //如果找到相同字符，进行状态转移
				if (chr[i-1] == chr[j-1]) {
					dp[j] = Math.min(dp[j],dp[i-1] + 1);
				}
			}
		}
		System.out.println(dp[s.length()]);
	}
}