最优包含 DP

最优包含题目描述给定两个字符串 S 和 T要求最少修改 S 中的多少个字符能使 S 包含 T。其中T 是 S 的子序列即可以从 S 中抽出若干个字符按原来的顺序组合成一个新的字符串与 T 完全一样。输入输出样例输入ABCDEABCD XAABZ输出3解题思路题目意思是从 S 里面挑字符可以跳过按顺序拼出 T并且尽量少改字符他是一个选与不选的问题可以使用动态规划。定义dp[i][j] 表示 S 的前 i 个字符包含 T 的前 j 个字符所需的最少修改次数。初始化dp[0][0] 0dp[i][0] 0T 为空字符串时不需要修改dp[0][j] infS 为空字符串时无法包含非空 T状态转移方程如果 S[i-1] T[j-1]则 dp[i][j] dp[i-1][j-1]否则dp[i][j] min(dp[i-1][j-1] 1, dp[i-1][j])例子S “abc”T “ac”初始化i\j01200∞∞102030最终i\j01200∞∞100∞20013000代码实现#includeiostream#includestring#includevector#includealgorithmusingnamespacestd;#defineinf1005intmain(){string S,T;cinST;intnS.length();intmT.length();vectorvectorintdp(n1,vectorint(m1,inf));// 初始化for(inti0;in;i)dp[i][0]0;dp[0][0]0;// DPfor(inti1;in;i){for(intj1;jm;j){dp[i][j]min(dp[i-1][j-1](S[i-1]!T[j-1]),// 选S[i-1]dp[i-1][j]// 不选S[i-1]);}}coutdp[n][m]endl;return0;}