力扣11.4

97. 交错字符串

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

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空
子字符串
：

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

数据范围

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成

分析

记忆化搜索， $d p (i, j, k)$ 表示 $s 3$ 的前 $k$ 个字符能否由 $s 1$ 的前 $i$ 个和 $s 2$ 的前 $j$ 个交错构成，若

$s 3 [k] == s 1 [i]$ ，则 $df s (i + 1, j, k + 1)$
$s 3 [k] == s 2 [j]$ ，则 $df s (i, j + 1, k + 1)$

代码

class Solution {
public:
    const static int N = 105;
    int dp[N][N][2 * N];
    int dfs(int i1, int i2, int i3, string s1, string s2, string s3) {
        if(i3 == s3.size() && i1 == s1.size() && i2 == s2.size()) return true;
        if(i1 > s1.size() || i2 > s2.size()) return false;
        int &res = dp[i1][i2][i3];
        if(res != -1) return res;
        res = 0;
        if(s3[i3] == s1[i1]) {
            if(dfs(i1 + 1, i2, i3 + 1, s1, s2, s3)) res = 1;
        } 
        if(s3[i3] == s2[i2]) {
            if(dfs(i1, i2 + 1, i3 + 1, s1, s2, s3)) res = 1;
        }
        return res;
    }
    bool isInterleave(string s1, string s2, string s3) {
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
        memset(dp, -1, sizeof(dp));
        if(n3 != n1 + n2) return false;
        // dp[0][0][0] = true;
        bool res = dfs(0, 0, 0, s1, s2, s3);
        return res;
    }
};

583. 两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

数据范围

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

分析

求出两个单词的最长公共子序列长度为 $k$ ，最后结果为 $w or d 1. s i ze () + w or d 2. s i ze () - 2 * k$

代码

class Solution {
public:
    const static int N = 505;
    int dp[N][N];
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j < m; j ++ ) {
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
                if(word1[i] == word2[j]) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
            }
        }
        return n + m - 2 * dp[n][m];
    }
};

2218. 从栈中取出 K 个硬币的最大面值和

一张桌子上总共有 n 个硬币栈。每个栈有正整数个带面值的硬币。

每一次操作中，你可以从任意一个栈的顶部取出 1 个硬币，从栈中移除它，并放入你的钱包里。

给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里从顶到底的硬币面值。同时给你一个正整数 k ，请你返回在恰好进行 k 次操作的前提下，你钱包里硬币面值之和最大为多少。

数据范围

n == piles.length
1 <= n <= 1000
1 <= piles[i][j] <= 105
1 <= k <= sum(piles[i].length) <= 2000

分析

这题可以转化为分组背包，预处理每个栈的前缀和，每个前缀和实际就是每个组的物品，且每组只能选一个

代码

class Solution {
public:
    const static int N = 1005;
    int dp[N][N * 2];
    vector<vector<int>> pre;
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        int n = piles.size();
        pre.resize(n);
        for(int i = 0; i < n; i ++ ) {
            pre[i].resize(piles[i].size());
            for(int j = 0; j < piles[i].size(); j ++ ) {
                if(j == 0) pre[i][j] = piles[i][j];
                else pre[i][j] = pre[i][j - 1] + piles[i][j];
            }
        }
        memset(dp, -0x3f, sizeof(dp));
        dp[0][0] = 0;
        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j <= k; j ++ ) {
                dp[i + 1][j] = dp[i][j];
                for(int z = 0; z < pre[i].size(); z ++ ) {
                    if(j >= z + 1) {
                        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - z - 1] + pre[i][z]);
                    }
                }
            }
        }
        return dp[n][k];
    }
};