小红书9.12 笔试第二题
给定一个非空字符串s，切割成若干个首尾相同的非空子串，求最少字串数量。
样例：
abaccd
输出：
3
100%AC答案：
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()]);
}
} 
