【动态规划】两个数组的 dp 问题
【动态规划】两个数组的 dp 问题
1. 最长公共子序列
状态表示：
dp[i][j] 表示 s1 的 0 ~ i 区间和 s2 的 0 ~ j 区间内所有子序列中，最长公共子序列的长度
状态转移方程：
当 s1[i] 和 s2[j] 相等时，那么最长公共子序列一定是以这两个位置为结尾的，所以就可以直接取 i - 1 ~ j - 1 区间内再去找，dp[i - 1][j - 1] 的结果加上确定好的 1 即可，如果不相等的话，就可以去 s1 的 i - 1 位置和 s2 的 j 继续找，或者是从 s1 的 i 位置和 s2 的 j - 1位置找，i - 1, j - 1 的情况已经被包含在这两种情况中了，所以可以不考虑这种情况，上面的情况找出最大值就是不相等时的 dp[i][j]
初始化：为了防止不越界，可以把数组多开一行和一列，初始化为 0 即可
填表顺序：从左到右，从上到下
返回值：dp[m][n]
class Solution {
public int longestCommonSubsequence(String t1, String t2) {
int m = t1.length(),n = t2.length();
char[] s1 = t1.toCharArray();
char[] s2 = t2.toCharArray();
int[][] dp = new int[m + 1][n + 1];
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
if(s1[i - 1] == s2[j - 1]){
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];
}
}2. 不相交的线
和上一题一样
3. 不同的子序列
状态表示：
dp[i][j] ：s 字符串[0 , j] 区间内所有的子序列中，有多少个 t 字符 [0 , i] 区间内的子串
当 t[i] ≠ s[j] 时，就要从 j - 1 位置开始找，因为需要找到子串 t 区间是连续的，所以 i 位置不能动，也就是 dp[i][j] = dp[i][j - 1]，如果 t[i] = s[j] 时，那么就还需要加上 dp[i - 1][j - 1]
初始化：为了防止越界，需要多开一行和一列，那么 i = 0 时，也就是 t 是空串的话，s 中枚举到哪个位置都是会包含一种方案的，也就是 i = 0 时都需要初始化为 1
填表顺序：从左到右，从上到下
返回值：dp[n][m]
class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
int[][] dp = new int[n + 1][m + 1];
for(int i = 0;i < m + 1;i++){
dp[0][i] = 1;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;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[n][m];
}
}4. 通配符匹配
状态表示：
dp[i][j] 表示字符串 p [0 , j ] 区间内是否能匹配字符串 s 区间 [0 , i ] 区间内的子串
状态转移方程：
字符串 p 的 j 位置可以分为普通字符，? ，* 三种情况，当是普通字符时，就需要判断 s[i] 和 p[j] 是否相等，如果相等，并且 dp[i - 1][j - 1] 也是 true ，那么 dp[i][j] 就是 true，如果是 ? 的话，直接就等于 dp[i][j]，如果是 * 的话，由于 * 可以匹配任意个字符，所以可以由之前的任意状态表示，但是这么多状态如果用循环来表示的话就可能超时，这种情况是可以优化一下的
可以通过数学变换来得出 dp[i][j] 是等于 dp[i][j] || dp[i - 1][j] 的
还可以用另一种思路：
' * ' 可以匹配空串，此时就要往 dp[i][j - 1] 中找答案，也可以匹配一个字符，但是不舍去，下一次还可以用来匹配一个字符或者空串，这样就达到了匹配多个字符的效果
初始化：可以通过引入空串的方式来初始化，防止填表时越界
(0 , 0 ) 位置肯定就是 true ，因为引入空串之后两个字符的 0 下标都是空字符串，可以匹配，但是当 j++ 时，也就是字符串 p 之后是 * 的话才能匹配空串，只要遇到不是 * ，后面都是 false，而第一列 1 下标之后，表示 p 的空串去匹配字符串 s ，肯定都是 false
填表顺序：从左到右
返回值：dp[m][n]
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(),n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
s = " " + s;
p = " " + p;
dp[0][0] = true;
int index = 1;
while(index <= n){
if(p.charAt(index) == '*'){
dp[0][index] = true;
index++;
}else{
break;
}
}
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
if(p.charAt(j) == '*'){
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}else{
if(p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}5. 正则表达式匹配
状态表示：
dp[i][j] 表示字符串 p[0 , j] 区间内的子串能否匹配字符串 s [0 , i ] 区间内的子串
状态转移方程：
根据最后一个字符的状态可以分为下面这几种情况
当字符串 p 最后一个字符是字母时，就需要判断是否和字符串 s 的 i 位置字符相等，相等的话就可以根据 dp[i - 1][j - 1] 来更新状态，如果是 ' . ' 的话，直接可以根据 dp[i - 1][j - 1] 来更新状态，如果是 ' * ' 的话，就需要考虑前一个字符是字母还是 ' . '，如果是 ' . ' 的话，就可以选择匹配空串，或者多个字符，就能更新出一堆状态，对于这样的状态表示，可以用上一题一样的优化方式，优化为 dp[i - 1][j] ，如果是字母的话，就需要判断是否能和 i 位置字符相等，然后选择匹配几个，同理，这种状态表示也可以优化为 dp[i - 1][j]
初始化：
第一列，也就是 p 是空串，这样除非 s 也是空串，否则怎么也不会匹配成功，所以只有 dp[0][0] 是 true，而对于第一行，如果说连续的偶数位上的字符是 ' * ' 的话，那么就可以带上前面的字符一起匹配空串，只要发现不是连续的偶数位，后面就都是 false
填表顺序：从上到下，从左到右
返回值：dp[m][n]
class Solution {
public boolean isMatch(String ss, String pp) {
int m = ss.length(),n = pp.length();
ss = " " + ss;
pp = " " + pp;
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
boolean[][] dp = new boolean[m + 1][n + 1];
//初始化
for (int i = 2; i <= n; i += 2){
if(p[i] == '*'){
dp[0][i] = true;
}else{
break;
}
}
dp[0][0] = true;
//填表
for (int i = 1; i <= m; i++){
for (int j = 1; j <= n; j++){
if (p[j] == '*'){
dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (p[j - 1] == '.' ||p[j - 1] == s[i]));
}else{
dp[i][j] = dp[i - 1][j - 1] && (p[j] == s[i] || p[j] == '.');
}
}
}
return dp[m][n];
}
}6. 交错字符串
状态表示：
为了方便进行表示，可以把三个字符串前面都加上一个空串，来更好的进行初始化和状态表示
dp[i][j] 表示 s1 中 [1 , i ] 区间内的字符串以及 s2 [ 1 , j ] 区间内的字符串，能否拼接成 s3 [1 , i + j ] 区间内的字符串
状态转移方程：
如果能拼接成功的话， s3 的最后一个位置一定是 s1 或者 s2 的最后一个字符，所以就可以分为两种情况，如果是 s1 的话，那么 dp[i][j] 就等于 dp[i - 1][j]，同理，如果是 s2 的话，那么就是 dp[i][j - 1]
初始化：
初始化的时候，dp[0][i] 就表示 s1 是空串的情况，此时就是判断 s2 和 s3 各个位置上的字符是否相等，当遇到不相等的，后面所有的位置就都是 false, 同理，dp[i][0] 就表示 s2 是空串的情况
填表顺序：填当前位置时需要用到上一个位置的值，所以从上往下，从左往右依次填表
返回值：dp[m][n]
还有一个注意点就是，刚开始一定要判断如果 s1 和 s2 的长度和如果和 s3 的长度不相等就直接返回 false，不只是优化的问题，如果不添加的话，后续的填表也会有问题的
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 i = 1; i <= n; i++) {
if (s2.charAt(i) == s3.charAt(i)){
dp[0][i] = true;
}else{
break;
}
}
for(int i = 1;i <= m;i++){
if(s1.charAt(i) == s3.charAt(i)){
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) == s3.charAt(i + j) && dp[i - 1][j])||
(s2.charAt(j) == s3.charAt(i + j) && dp[i][j - 1]);
}
}
return dp[m][n];
}
}7. 两个字符串的最小ASCII删除和
题中要求的是最小的 ASCII 删除和使剩下的字符串相等，那么就可以转化为公共子序列中最大的 ASCII 和，这样删除的 ASCII 和肯定就是最小的
状态表示：
dp[i][j] 表示 s1 的 [0 , i ] 区间和 s2 [0 , j ] 区间内的所有子序列中，公共子序列的 ASCII 最大和
状态转移方程：
可以分为四种情况，公共子序列中同时含有 s1 和 s2 的 i , j 位置的字符，以及只含其中一个，还有都不含的情况，由于是找最大值，都不包含的情况是被包含到只含一个的情况的，所以只需要求出前面三种情况的最大值即可
填表顺序：从左到右，从上到下
返回值：需要求出两个字符串的 ASCII 和，然后减去两倍的最大公共子序列的 ASCII 和
class Solution {
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length(),n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
if(s1.charAt(i - 1) == s2.charAt(j - 1))
dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - 1] + s1.charAt(i - 1));
}
}
int sum = 0;
for(char c : s1.toCharArray()) sum += c;
for(char c : s2.toCharArray()) sum += c;
return sum - 2 * dp[m][n];
}
}腾讯云开发者
