校园网站建设方案,个人网站开发赚钱方向,如何做英文网站的中文网,wordpress创建自定义页面模板class068 更多的动态规划【算法】
算法讲解068【必备】见识更多二维动态规划题目 code1 115. 不同的子序列
// 不同的子序列 // 给你两个字符串 s 和 t #xff0c;统计并返回在 s 的 子序列 中 t 出现的个数 // 测试链接 : https://leetcode.cn/problems/distinct-subseque…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.lengths2.lengths3.length dp[i][j]s1[前i个]和s2[前j个]组成s3[前ij个] s1[i-1]s3[ij-1]dp[i-1][j] || s2[j-1]s3[ij-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[前缀长度为ij]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-j1)
第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) {ListString 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子序列strreturn s1.length() - str.length();}}return s1.length();}// 生成s1字符串的所有子序列串public static void f(char[] s1, int i, String path, ListString 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(测试结束);}}
