func minDistance(word1 string, word2 string) int {
	// dp[i][j] means the LCS of s1[0:i] && s2[0:j],
	// then if s1[i] == s2[j], dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
	// else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
	m, n := len(word1), len(word2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := range word1 {
		for j := range word2 {
			if word1[i] == word2[j] {
				dp[i+1][j+1] = maxInt(dp[i+1][j+1], dp[i][j]+1)
			} else {
				dp[i+1][j+1] = maxInt(dp[i][j+1], dp[i+1][j])
			}
		}
	}
	return m + n - 2*dp[m][n]
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}