一、题目

https://www.acwing.com/problem/content/904/
image.png

二、思想

f[i][j]为a的前i个子母等于b的前j个字母所需要的操作次数的集合，题目要求的是最小值，针对a的前i个字母变成b的前j个字母有三种操作方式

  1. 增：可以由a的前i个字母末尾增加一个b[j]来实现，可以用f[i][j-1]+1表示，加的那个1是本次增加操作的操作次数 :::info 因为f[i][j-1]所表示的是a的前i个子母等于b的前j-1个字母所需要的操作次数的集合的最小值，f[i][j-1]是使他们相等的操作次数，所以a的前i个子母跟b的前j-1个字母一定是相等的，只需要考虑a[i]和b[j]即可
    动规即只考虑这个当前情况，由哪个状态转换过来默认这个状态已经是满足题意的了 :::

  2. 删：可以由a的前i个字母末尾减少一个a[i]来实现，可以用f[i-1][j]+1表示

  3. 改：改分两种情况
  • 若a[i]和b[j]相等，那就不用改，只需要保证a的前i-1个字母与b的前j-1个字母相等即可，所以可以用f[i-1][j-1]表示
  • 若a[i]和b[j]不相等，那就需要把a[i]改成b[j]，并且需要保证a的前i-1个字母与b的前j-1个字母相等即可，所以可以用f[i-1][j-1]+1表示

这三种情况都能使a的前i个子母等于b的前j个字母，所以三个操作取最小值即可
IMG_0036.JPG

三、代码 O(n2)

  1. import java.util.Scanner;
  2. public class Main {
  3.     public static void main(String[] args) {
  4.         Scanner in = new Scanner(System.in);
  5.         int n = in.nextInt();
  6.         String a_s = in.next();
  7.         int m = in.nextInt();
  8.         String b_s = in.next();
  9.         int[][] f = new int[1005][1005];
  10.         char[] a = new char[1005];
  11.         char[] b = new char[1005];
  12.         for (int i = 1; i <= n; i++) a[i] = a_s.charAt(i-1);
  13.         for (int i = 1; i <= m; i++) b[i] = b_s.charAt(i-1);
  15.         // 初始化
  16.         // a的前0个字母要与b的前i个字母相同需要进行i次“增加”操作
  17.         for (int i = 0; i <= m; i++) f[0][i] = i;
  18.         // a的前i个字母要与b的前0个字母相同需要进行i次“删除”操作
  19.         for (int i = 0; i <= n; i++) f[i][0] = i;
  21.         for (int i = 1; i <= n; i++) {
  22.             for (int j = 1; j <= m; j++) {
  24.                 f[i][j] = Math.min(f[i][j-1]+1,f[i-1][j]+1);
  26.                 if(a[i] == b[j]) f[i][j] = Math.min(f[i][j], f[i-1][j-1]);
  27.                 else f[i][j] = Math.min(f[i][j], f[i-1][j-1] +1);
  28.             }
  29.         }
  30.         System.out.println(f[n][m]);
  32.     }
  33. }

四、代码空间优化

  1. import java.util.Scanner;
  2. public class Main {
  3.     public static void main(String[] args) {
  4.         Scanner in = new Scanner(System.in);
  5.         int n = in.nextInt();
  6.         String a = in.next();
  7.         int m = in.nextInt();
  8.         String b = in.next();
  9.         int[][] f = new int[1005][1005];
  11.         // 初始化
  12.         // a的前0个字母要与b的前i个字母相同需要进行i次“增加”操作
  13.         for (int i = 0; i <= m; i++) f[0][i] = i;
  14.         // a的前i个字母要与b的前0个字母相同需要进行i次“删除”操作
  15.         for (int i = 0; i <= n; i++) f[i][0] = i;
  17.         for (int i = 1; i <= n; i++) {
  18.             for (int j = 1; j <= m; j++) {
  19.                 f[i][j] = Math.min(f[i][j-1]+1,f[i-1][j]+1);
  20.                 f[i][j] = Math.min(f[i][j], f[i-1][j-1] + ((a.charAt(i-1) != b.charAt(j-1))? 1 : 0));
  21.             }
  22.         }
  23.         System.out.println(f[n][m]);
  25.     }