#include #include #include #include using namespace std; #define REP(i,s,e) for (i = s; i <= e; i++) #define rep(i,n) REP (i,0,(int)(n)-1) #define RREP(i,s,e) for (i = s; i >= e; i--) #define rrep(i,n) RREP (i,(int)(n)-1,0) #define INF (int)1e8 #define MOD (int)1e9+7 int dp[1001][1001]; int main(void) { int i, j, n, m; string s, t; cin >> n >> m >> s >> t; REP (i,0,n) dp[i][0] = i; REP (j,0,m) dp[0][j] = j; REP (i,1,n) { REP (j,1,m) { if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = dp[i-1][j-1]+1; dp[i][j] = min({dp[i][j],dp[i-1][j]+1,dp[i][j-1]+1}); } } cout << dp[n][m] << endl; return 0; }