class068 更多的动态规划【算法】-阿里云开发者社区

class068 更多的动态规划【算法】

算法讲解068【必备】见识更多二维动态规划题目

code1 115. 不同的子序列

// 不同的子序列

// 给你两个字符串 s 和 t ，统计并返回在 s 的子序列中 t 出现的个数

// 测试链接 : https://leetcode.cn/problems/distinct-subsequences/

dp[i][j]：s[前i个]子序列能够出现t[前j个]的个数

=dp[i-1][j]

+=dp[i-1][j-1] , s[i-1]==t[j-1]

第0行，0

第0列，1

code1 动态规划

code2 空间压缩

package class068;
// 不同的子序列
// 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences/
public class Code01_DistinctSubsequences {
  // 已经展示太多次从递归到动态规划了
  // 直接写动态规划吧
  public static int numDistinct1(String str, String target) {
    char[] s = str.toCharArray();
    char[] t = target.toCharArray();
    int n = s.length;
    int m = t.length;
    // dp[i][j] :
    // s[前缀长度为i]的所有子序列中，有多少个子序列等于t[前缀长度为j]
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= n; i++) {
      dp[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        dp[i][j] = dp[i - 1][j];
        if (s[i - 1] == t[j - 1]) {
          dp[i][j] += dp[i - 1][j - 1];
        }
      }
    }
    return dp[n][m];
  }
  // 空间压缩
  public static int numDistinct2(String str, String target) {
    char[] s = str.toCharArray();
    char[] t = target.toCharArray();
    int n = s.length;
    int m = t.length;
    int[] dp = new int[m + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
      for (int j = m; j >= 1; j--) {
        if (s[i - 1] == t[j - 1]) {
          dp[j] += dp[j - 1];
        }
      }
    }
    return dp[m];
  }
}

code2 72. 编辑距离

// 编辑距离

// 给你两个单词 word1 和 word2

// 请返回将 word1 转换成 word2 所使用的最少代价

// 你可以对一个单词进行如下三种操作：

// 插入一个字符，代价a

// 删除一个字符，代价b

// 替换一个字符，代价c

// 测试链接 : https://leetcode.cn/problems/edit-distance/

dp[i][j]：word1[前i个]能够转换word2[前j个]

dp[i-1][j-1] , word1[i-1]==word2[j-1]

dp[i][j-1]+a，插入

dp[i-1][j]+b，删除

dp[i-1][j-1]+c，替换word1[i-1]!=word2[j-1]

第0行，插入j个

第0列，删除i个

code1 动态规划

code2 空间压缩

package class068;
// 编辑距离
// 给你两个单词 word1 和 word2
// 请返回将 word1 转换成 word2 所使用的最少代价
// 你可以对一个单词进行如下三种操作：
// 插入一个字符，代价a
// 删除一个字符，代价b
// 替换一个字符，代价c
// 测试链接 : https://leetcode.cn/problems/edit-distance/
public class Code02_EditDistance {
  // 已经展示太多次从递归到动态规划了
  // 直接写动态规划吧
  public int minDistance(String word1, String word2) {
    return editDistance2(word1, word2, 1, 1, 1);
  }
  // 原初尝试版
  // a : str1中插入1个字符的代价
  // b : str1中删除1个字符的代价
  // c : str1中改变1个字符的代价
  // 返回从str1转化成str2的最低代价
  public static int editDistance1(String str1, String str2, int a, int b, int c) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int n = s1.length;
    int m = s2.length;
    // dp[i][j] :
    // s1[前缀长度为i]想变成s2[前缀长度为j]，至少付出多少代价
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
      dp[i][0] = i * b;
    }
    for (int j = 1; j <= m; j++) {
      dp[0][j] = j * a;
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        int p1 = Integer.MAX_VALUE;
        if (s1[i - 1] == s2[j - 1]) {
          p1 = dp[i - 1][j - 1];
        }
        int p2 = Integer.MAX_VALUE;
        if (s1[i - 1] != s2[j - 1]) {
          p2 = dp[i - 1][j - 1] + c;
        }
        int p3 = dp[i][j - 1] + a;
        int p4 = dp[i - 1][j] + b;
        dp[i][j] = Math.min(Math.min(p1, p2), Math.min(p3, p4));
      }
    }
    return dp[n][m];
  }
  // 枚举小优化版
  // a : str1中插入1个字符的代价
  // b : str1中删除1个字符的代价
  // c : str1中改变1个字符的代价
  // 返回从str1转化成str2的最低代价
  public static int editDistance2(String str1, String str2, int a, int b, int c) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int n = s1.length;
    int m = s2.length;
    // dp[i][j] :
    // s1[前缀长度为i]想变成s2[前缀长度为j]，至少付出多少代价
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
      dp[i][0] = i * b;
    }
    for (int j = 1; j <= m; j++) {
      dp[0][j] = j * a;
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        if (s1[i - 1] == s2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = Math.min(Math.min(dp[i - 1][j] + b, dp[i][j - 1] + a), dp[i - 1][j - 1] + c);
        }
      }
    }
    return dp[n][m];
  }
  // 空间压缩
  public static int editDistance3(String str1, String str2, int a, int b, int c) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int n = s1.length;
    int m = s2.length;
    int[] dp = new int[m + 1];
    for (int j = 1; j <= m; j++) {
      dp[j] = j * a;
    }
    for (int i = 1, leftUp, backUp; i <= n; i++) {
      leftUp = (i - 1) * b;
      dp[0] = i * b;
      for (int j = 1; j <= m; j++) {
        backUp = dp[j];
        if (s1[i - 1] == s2[j - 1]) {
          dp[j] = leftUp;
        } else {
          dp[j] = Math.min(Math.min(dp[j] + b, dp[j - 1] + a), leftUp + c);
        }
        leftUp = backUp;
      }
    }
    return dp[m];
  }
}

code3 97. 交错字符串

// 交错字符串

// 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的

// 测试链接 : https://leetcode.cn/problems/interleaving-string/

前提：s1.length+s2.length==s3.length

dp[i][j]：s1[前i个]和s2[前j个]组成s3[前i+j个]

s1[i-1]==s3[i+j-1]&&dp[i-1][j]

|| s2[j-1]==s3[i+j-1]&&dp[i][j-1]

第0行 s2匹配s3

第0列 s1匹配s3

code1 动态规划

code2 空间压缩

package class068;
// 交错字符串
// 给定三个字符串 s1、s2、s3
// 请帮忙验证s3是否由s1和s2交错组成
// 测试链接 : https://leetcode.cn/problems/interleaving-string/
public class Code03_InterleavingString {
  // 已经展示太多次从递归到动态规划了
  // 直接写动态规划吧
  public static boolean isInterleave1(String str1, String str2, String str3) {
    if (str1.length() + str2.length() != str3.length()) {
      return false;
    }
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    char[] s3 = str3.toCharArray();
    int n = s1.length;
    int m = s2.length;
    // dp[i][j]:
    // s1[前缀长度为i]和s2[前缀长度为j]，能否交错组成出s3[前缀长度为i+j]
    boolean[][] dp = new boolean[n + 1][m + 1];
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
      if (s1[i - 1] != s3[i - 1]) {
        break;
      }
      dp[i][0] = true;
    }
    for (int j = 1; j <= m; j++) {
      if (s2[j - 1] != s3[j - 1]) {
        break;
      }
      dp[0][j] = true;
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]);
      }
    }
    return dp[n][m];
  }
  // 空间压缩
  public static boolean isInterleave2(String str1, String str2, String str3) {
    if (str1.length() + str2.length() != str3.length()) {
      return false;
    }
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    char[] s3 = str3.toCharArray();
    int n = s1.length;
    int m = s2.length;
    boolean[] dp = new boolean[m + 1];
    dp[0] = true;
    for (int j = 1; j <= m; j++) {
      if (s2[j - 1] != s3[j - 1]) {
        break;
      }
      dp[j] = true;
    }
    for (int i = 1; i <= n; i++) {
      dp[0] = s1[i - 1] == s3[i - 1] && dp[0];
      for (int j = 1; j <= m; j++) {
        dp[j] = (s1[i - 1] == s3[i + j - 1] && dp[j]) || (s2[j - 1] == s3[i + j - 1] && dp[j - 1]);
      }
    }
    return dp[m];
  }
}

code4 有效涂色问题

// 有效涂色问题

// 给定n、m两个参数

// 一共有n个格子，每个格子可以涂上一种颜色，颜色在m种里选

// 当涂满n个格子，并且m种颜色都使用了，叫一种有效方法

// 求一共有多少种有效的涂色方法

// 1 <= n, m <= 5000

// 结果比较大请 % 1000000007 之后返回

// 对数器验证

dp[i][j]：前i个格子有j种颜色的涂法

+=dp[i-1][j] * m

+=dp[i][j-1] * (m-j+1)

第1行：0

第1列: m

package class068;
import java.util.Arrays;
// 有效涂色问题
// 给定n、m两个参数
// 一共有n个格子，每个格子可以涂上一种颜色，颜色在m种里选
// 当涂满n个格子，并且m种颜色都使用了，叫一种有效方法
// 求一共有多少种有效的涂色方法
// 1 <= n, m <= 5000
// 结果比较大请 % 1000000007 之后返回
// 对数器验证
public class Code04_FillCellsUseAllColorsWays {
  // 暴力方法
  // 为了验证
  public static int ways1(int n, int m) {
    return f(new int[n], new boolean[m + 1], 0, n, m);
  }
  // 把所有填色的方法暴力枚举
  // 然后一个一个验证是否有效
  // 这是一个带路径的递归
  // 无法改成动态规划
  public static int f(int[] path, boolean[] set, int i, int n, int m) {
    if (i == n) {
      Arrays.fill(set, false);
      int colors = 0;
      for (int c : path) {
        if (!set[c]) {
          set[c] = true;
          colors++;
        }
      }
      return colors == m ? 1 : 0;
    } else {
      int ans = 0;
      for (int j = 1; j <= m; j++) {
        path[i] = j;
        ans += f(path, set, i + 1, n, m);
      }
      return ans;
    }
  }
  // 正式方法
  // 时间复杂度O(n * m)
  // 已经展示太多次从递归到动态规划了
  // 直接写动态规划吧
  // 也不做空间压缩了，因为千篇一律
  // 有兴趣的同学自己试试
  public static int MAXN = 5001;
  public static int[][] dp = new int[MAXN][MAXN];
  public static int mod = 1000000007;
  public static int ways2(int n, int m) {
    // dp[i][j]:
    // 一共有m种颜色
    // 前i个格子涂满j种颜色的方法数
    for (int i = 1; i <= n; i++) {
      dp[i][1] = m;
    }
    for (int i = 2; i <= n; i++) {
      for (int j = 2; j <= m; j++) {
        dp[i][j] = (int) (((long) dp[i - 1][j] * j) % mod);
        dp[i][j] = (int) ((((long) dp[i - 1][j - 1] * (m - j + 1)) + dp[i][j]) % mod);
      }
    }
    return dp[n][m];
  }
  public static void main(String[] args) {
    // 测试的数据量比较小
    // 那是因为数据量大了，暴力方法过不了
    // 但是这个数据量足够说明正式方法是正确的
    int N = 9;
    int M = 9;
    System.out.println("功能测试开始");
    for (int n = 1; n <= N; n++) {
      for (int m = 1; m <= M; m++) {
        int ans1 = ways1(n, m);
        int ans2 = ways2(n, m);
        if (ans1 != ans2) {
          System.out.println("出错了!");
        }
      }
    }
    System.out.println("功能测试结束");
    System.out.println("性能测试开始");
    int n = 5000;
    int m = 4877;
    System.out.println("n : " + n);
    System.out.println("m : " + m);
    long start = System.currentTimeMillis();
    int ans = ways2(n, m);
    long end = System.currentTimeMillis();
    System.out.println("取余之后的结果 : " + ans);
    System.out.println("运行时间 : " + (end - start) + " 毫秒");
    System.out.println("性能测试结束");
  }
}

code5 最少删除多少字符可以变成子串

// 最少删除多少字符可以变成子串

// 给定两个字符串s1和s2

// 返回s1至少删除多少字符可以成为s2的子串

// 对数器验证

dp[i][j]：s1[前i个]成为s2[前j个]任意后缀串至少删除字符的个数

dp[i-1][j-1],s1[i-1]==s2[j-1]

dp[i-1][j]+1

第0行：0

第0列：i

返回dp[n][…]中最小的

package class068;
import java.util.ArrayList;
import java.util.List;
// 删除至少几个字符可以变成另一个字符串的子串
// 给定两个字符串s1和s2
// 返回s1至少删除多少字符可以成为s2的子串
// 对数器验证
public class Code05_MinimumDeleteBecomeSubstring {
  // 暴力方法
  // 为了验证
  public static int minDelete1(String s1, String s2) {
    List<String> list = new ArrayList<>();
    f(s1.toCharArray(), 0, "", list);
    // 排序 : 长度大的子序列先考虑
    // 因为如果长度大的子序列是s2的子串
    // 那么需要删掉的字符数量 = s1的长度 - s1子序列长度
    // 子序列长度越大，需要删掉的字符数量就越少
    // 所以长度大的子序列先考虑
    list.sort((a, b) -> b.length() - a.length());
    for (String str : list) {
      if (s2.indexOf(str) != -1) {
        // 检查s2中，是否包含当前的s1子序列str
        return s1.length() - str.length();
      }
    }
    return s1.length();
  }
  // 生成s1字符串的所有子序列串
  public static void f(char[] s1, int i, String path, List<String> list) {
    if (i == s1.length) {
      list.add(path);
    } else {
      f(s1, i + 1, path, list);
      f(s1, i + 1, path + s1[i], list);
    }
  }
  // 正式方法，动态规划
  // 已经展示太多次从递归到动态规划了
  // 直接写动态规划吧
  // 也不做空间压缩了，因为千篇一律
  // 有兴趣的同学自己试试
  public static int minDelete2(String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int n = s1.length;
    int m = s2.length;
    // dp[len1][len2] :
    // s1[前缀长度为i]至少删除多少字符，可以变成s2[前缀长度为j]的任意后缀串
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
      dp[i][0] = i;
      for (int j = 1; j <= m; j++) {
        if (s1[i - 1] == s2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = dp[i - 1][j] + 1;
        }
      }
    }
    int ans = Integer.MAX_VALUE;
    for (int j = 0; j <= m; j++) {
      ans = Math.min(ans, dp[n][j]);
    }
    return ans;
  }
  // 为了验证
  // 生成长度为n，有v种字符的随机字符串
  public static String randomString(int n, int v) {
    char[] ans = new char[n];
    for (int i = 0; i < n; i++) {
      ans[i] = (char) ('a' + (int) (Math.random() * v));
    }
    return String.valueOf(ans);
  }
  // 为了验证
  // 对数器
  public static void main(String[] args) {
    // 测试的数据量比较小
    // 那是因为数据量大了，暴力方法过不了
    // 但是这个数据量足够说明正式方法是正确的
    int n = 12;
    int v = 3;
    int testTime = 20000;
    System.out.println("测试开始");
    for (int i = 0; i < testTime; i++) {
      int len1 = (int) (Math.random() * n) + 1;
      int len2 = (int) (Math.random() * n) + 1;
      String s1 = randomString(len1, v);
      String s2 = randomString(len2, v);
      int ans1 = minDelete1(s1, s2);
      int ans2 = minDelete2(s1, s2);
      if (ans1 != ans2) {
        System.out.println("出错了!");
      }
    }
    System.out.println("测试结束");
  }
}

class068 更多的动态规划【算法】