求java解决字符串最优包含问题

一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。
给定两个字符串 S 和 T，最少修改 S 中的多少个字符，能使 S 包含T ，T成为S中的子串？

输入格式：输入两个字符串S和T
输出格式：输出一个整数表示最少修改字符的次数

样例：
输入S：ABCDEABCD
输入T：XAABZ
输出：3

解法：动态规划。

建立一个二维数组dp[i][j]，表示S的前i个字符和T的前j个字符的最少修改次数。
dp[i][j]表示S[0..i]和T[0..j]之间最少修改字符的次数，

如果S[i]==T[j]，则dp[i][j] = dp[i-1][j-1]；

如果S[i]!=T[j]，则dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。

最终结果为dp[m][n]，其中m为S的长度，n为T的长度。

其实就是用T循环去跟S[0:4]、S[1:5]、S[2:6]。。。去比较，看S的哪个子串与T相同的字符最多
反过来就是需要修改的字符最少
substring一下就得到子串，循环判断一下就可以得到count