题目

类型：动态规划
image.png

解题思路

https://leetcode.cn/problems/edit-distance/solution/bian-ji-ju-chi-mian-shi-ti-xiang-jie-by-labuladong/

代码

  1. int minDistance(String s1, String s2) {
  2.     int m = s1.length(), n = s2.length();
  3.     int[][] dp = new int[m + 1][n + 1];
  4.     // base case 
  5.     for (int i = 1; i <= m; i++)
  6.         dp[i][0] = i;
  7.     for (int j = 1; j <= n; j++)
  8.         dp[0][j] = j;
  9.     // 自底向上求解
  10.     for (int i = 1; i <= m; i++)
  11.         for (int j = 1; j <= n; j++)
  12.             if (s1.charAt(i-1) == s2.charAt(j-1))
  13.                 dp[i][j] = dp[i - 1][j - 1];
  14.             else               
  15.                 dp[i][j] = min(
  16.                     dp[i - 1][j] + 1,
  17.                     dp[i][j - 1] + 1,
  18.                     dp[i-1][j-1] + 1
  19.                 );
  20.     // 储存着整个 s1 和 s2 的最小编辑距离
  21.     return dp[m][n];
  22. }
  24. int min(int a, int b, int c) {
  25.     return Math.min(a, Math.min(b, c));
  26. }