? tips
1.考慮空串，即dp表多出一行一列， 代表某個字符串為空。
2.考慮最后一個位置；是否相等；
3.可在字符串最前面加虛擬位置以對應(yīng)映射關(guān)系；
4.一般橫行是j，列是i。此時第一行代表第二個字符串不為空，即第一個字符串是空的
1.最長公共子序列
class Solution {
//dp[i][j]表s1的[0,i]以及s2的[0,j]所有子序列中最長公共子序列的長度；
//如果s[i]=s[j]，那公共序列一定是以i,j為結(jié)尾
public int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
s1 = " " + s1;
s2 = " " + s2;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i) == s2.charAt(j)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
//!=時，有[0,i-1]&[0,j],[0,i-1]&[0,j-1],[0,i]&[0,j-1];空串 StringBuilder sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (s1.charAt(i) == s2.charAt(j)) {
sb.insert(0, s1.charAt(i));
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
i--;
} else {
j--;
}
}
System.out.println( sb.toString());?2.最長重復(fù)子數(shù)組
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int m=nums1.length;int n=nums2.length;
int[][] dp=new int[m+1][n+1];
int ret=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(nums1[i-1]==nums2[j-1])
dp[i][j]=dp[i-1][j-1]+1;
ret=Math.max(ret,dp[i][j]);
}
}
return ret;
}
}class Solution {
public int[] findLength(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[][] dp = new int[m + 1][n + 1];
int maxLength = 0;
int endIndex = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endIndex = i - 1; // 結(jié)束索引
}
}
}
}
int[] result = new int[maxLength];
for (int i = endIndex - maxLength + 1; i <= endIndex; i++) {
result[i - (endIndex - maxLength + 1)] = nums1[i];
}
return result;
}
}
class Solution {
public int[] findLength(int[] nums1, int[] nums2) {
int maxLength = 0;
int endIndex = -1;
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
int len = 0;
while (i + len < nums1.length && j + len < nums2.length && nums1[i + len] == nums2[j + len]) {
len++;
}
if (len > maxLength) {
maxLength = len;
endIndex = i + maxLength - 1;
}
}
}
int[] result = new int[maxLength];
for (int i = endIndex - maxLength + 1; i <= endIndex; i++) {
result[i - (endIndex - maxLength + 1)] = nums1[i];
}
return result;
}
}3.不同的子序列
給你兩個字符串?
s?和?t?，統(tǒng)計(jì)并返回在?s?的?子序列?中?t?出現(xiàn)的個數(shù)，結(jié)果需要對?109?+ 7 取模。示例?1：
輸入：s = "rabbbit", t = "rabbit"輸出：3解釋： 如下所示, 有 3 種可以從 s 中得到"rabbit" 的方案。rabbbitrabbbitrabbbit
class Solution {
//dp[i][j]在s的[0,j]的子序列中出現(xiàn)t的[0,i]子串的個數(shù)
//是否包含字符s[j]
public int numDistinct(String s, String t) {
int m = t.length(), n = s.length();
int[][] dp = new int[m + 1][n + 1];
for (int j = 0; j <= n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i][j - 1];
if (t.charAt(i - 1) == s.charAt(j - 1)) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}?4.交錯字符串
給定三個字符串?
s1、s2、s3，請你幫忙驗(yàn)證?s3?是否是由?s1?和?s2?交錯?組成的。兩個字符串?
s?和?t?交錯?的定義與過程如下，其中每個字符串都會被分割成若干?非空?子字符串：
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- 交錯?是?
s1 + t1 + s2 + t2 + s3 + t3 + ...?或者?t1 + s1 + t2 + s2 + t3 + s3 + ...注意：
a + b?意味著字符串?a?和?b?連接。示例 1：
輸入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 輸出：true示例 2：
輸入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 輸出：false示例 3：
輸入：s1 = "", s2 = "", s3 = "" 輸出：true提示：
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1、s2、和?s3?都由小寫英文字母組成
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) {
return false;
}
s1 = "" + s1;
s2 = "" + s2;
s3 = "" + s3;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true; // 初始化第一個位置
for (int j = 1; j <= n; j++) { // 初始化第一行
if (s2.charAt(j - 1) == s3.charAt(j - 1)) {
dp[0][j] = true;
} else {
break;
}
}
for (int i = 1; i <= m; i++) { // 初始化第一列
if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
dp[i][0] = true;
} else {
break;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = (s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j])
|| (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]);
}
}
return dp[m][n];
}
}5.通配符匹配?
44. 通配符匹配https://leetcode.cn/problems/wildcard-matching/
給你一個輸入字符串 (
s) 和一個字符模式 (p) ，請你實(shí)現(xiàn)一個支持?'?'?和?'*'?匹配規(guī)則的通配符匹配：
'?'?可以匹配任何單個字符。'*'?可以匹配任意字符序列（包括空字符序列）。判定匹配成功的充要條件是：字符模式必須能夠?完全匹配?輸入字符串（而不是部分匹配）。
示例 1：
輸入：s = "aa", p = "a" 輸出：false 解釋："a" 無法匹配 "aa" 整個字符串。示例 2：
輸入：s = "aa", p = "*" 輸出：true 解釋：'*' 可以匹配任意字符串。示例 3：
輸入：s = "cb", p = "?a" 輸出：false 解釋：'?' 可以匹配 'c', 但第二個 'a' 無法匹配 'b
class Solution {
//主要是*可以匹配空符，1個，2個。。。。,s的[0,i],p的[0,j]
public boolean isMatch(String s, String p) {
if (p.equals("*")) return true;
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = true;
}else
break;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];//去一個空符+數(shù)學(xué)推導(dǎo)
}
}
}
return dp[m][n];
}
}6.兩個字符串的最小ASCII刪除和
712. 兩個字符串的最小ASCII刪除和https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/
給定兩個字符串
s1?和?s2，返回?使兩個字符串相等所需刪除字符的?ASCII?值的最小和?。示例 1:
輸入: s1 = "sea", s2 = "eat" 輸出: 231 解釋: 在 "sea" 中刪除 "s" 并將 "s" 的值(115)加入總和。 在 "eat" 中刪除 "t" 并將 116 加入總和。 結(jié)束時，兩個字符串相等，115 + 116 = 231 就是符合條件的最小和。示例?2:文章來源：http://www.zghlxwxcb.cn/news/detail-838249.html
輸入: s1 = "delete", s2 = "leet" 輸出: 403 解釋: 在 "delete" 中刪除 "dee" 字符串變成 "let"， 將 100[d]+101[e]+101[e] 加入總和。在 "leet" 中刪除 "e" 將 101[e] 加入總和。 結(jié)束時，兩個字符串都等于 "let"，結(jié)果即為 100+101+101+101 = 403 。 如果改為將兩個字符串轉(zhuǎn)換為 "lee" 或 "eet"，我們會得到 433 或 417 的結(jié)果，比答案更大。轉(zhuǎn)化：在兩個字符串中找出文章來源地址http://www.zghlxwxcb.cn/news/detail-838249.html
class Solution {
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int sum = 0;
for (int i = 0; i < m; i++) {
sum += (int) s1.charAt(i);
}
for (int i = 0; i < n; i++) {
sum += (int) s2.charAt(i);
}
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + (int) s1.charAt(i - 1);
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return sum - 2 * dp[m][n];
}
}
到了這里，關(guān)于兩個數(shù)組的動態(tài)規(guī)劃——最長公共子序列模型的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
