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 都由小写英文字母组成

分析

记忆化搜索，$dp(i,j,k)$表示$s3$的前$k$个字符能否由$s1$的前$i$个和$s2$的前$j$个交错构成，若

• $s3[k]==s1[i]$，则 $dfs(i+1,j,k+1)$
• $s3[k]==s2[j]$，则$dfs(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$，最后结果为$word1.size()+word2.size()-2\ast 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];
    }
};