链接72. 编辑距离 - 力扣LeetCodeclass Solution { public: int minDistance(string word1, string word2) { int len1 word1.size(); int len2 word2.size(); if(len1*len2 0) { return len1len2; } vectorvectorint dp(len11, vectorint(len21, 0)); // dp[i][j]表示word1[0...i-1]和word2[0...j-1]的编辑距离 for(int i 0; i len1; i) { dp[i][0] i; } for(int j 0; j len2; j) { dp[0][j] j; } for(int i 1; i len1; i) { for(int j 1; j len2; j) { if(word1[i-1] word2[j-1]) { dp[i][j] dp[i-1][j-1]; } else { dp[i][j] min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) 1; } } } return dp[len1][len2]; } };https://www.bilibili.com/video/BV1cb411u7uX