极简
文章
145
分类
10
评论
1

动态规划-贴纸拼词

| 数据结构与算法 •
字数总计 25045 | 阅读时长 62分钟 | 阅读量 69

题目描述

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。

示例：
输入：stickers = [“with”,“example”,“science”], target = “thehat”
输出：3
解释：我们可以使用 2 个 “with” 贴纸，和 1 个 “example” 贴纸，把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 。此外，这是形成目标字符串所需的最小贴纸数量。

暴力递归-从左到右

读完题目后我们可以知道这属于完全背包问题，因为每种贴纸可以无限取得。同样，从左到右选贴纸，每种贴纸“要”或“不要”，可以得到以下代码：

//返回值=target-sticker,即消耗贴纸
//比如target="helloworld",sticker="llld"
//则返回"heowor"
string minus(const string &sticker, string target)
{
    for (char c : sticker)
    {
        size_t pos = target.find(c);
        if (pos != string::npos)
            target.erase(pos, 1);
    }
    return target;
}
int process(const vector<string> &stickers, string target, int index)
{
    if (target.empty())
        return 0;//找到一种拼法
    if(index >= stickers.size())//不可置前
        return INT32_MAX; //说明此路径无法凑出target字符
    if(target == minus(stickers[index], target))//如果该贴纸不包含target所需字母
        return process(stickers, target, index + 1);//则前往下一种贴纸
    int a = process(stickers, target, index + 1);//即使此贴纸包含,我也可以不要,直接去下一种贴纸
    target = minus(stickers[index], target);//要此贴纸,则消耗
    int b = process(stickers, target, index);//继续在此贴纸中选择要或不要
    return std::min(a, b == INT32_MAX ? INT32_MAX : b + 1);//+1是因为我们消耗了1张贴纸
}
int minStickerNum(const vector<string> &stickers, string target)
{
    int ret = process(stickers, target, 0);
    return ret == INT32_MAX ? -1 : ret;
}

本题有许多细节值得注意：

  • 第 16 行和 18 行的两个 if 不能交换位置，原因是：递归函数是在上游（第 23 行）拼贴纸，在下游（第 16 行）检查 target 是否已经拼凑完毕；当 index 来到最后一种贴纸，且选择该贴纸后恰好拼凑完 target ，那么进入下一层递归时 index 就已经越界，但实际上我们已经找到了一种拼法。

  • 第 20 行的检查不可省略，否则程序流会反复进入最后一种贴纸，最后栈溢出。

  • 将无效值设为 INT32_MAX 是为了方便最后 a、b 的比较，否则就得写成这样：

    //....
if(index >= stickers.size())
        return -1; //无效值为-1
//....
if(a == -1 && b == -1)
    return -1;
else if(a == -1 && b != -1)
    return b + 1;
else if(a != -1 && b == -1)
    return a;
else
    return std::min(a, b + 1);

暴力递归-从左到右-优化

和完全背包不一样的是，这里我们要拼凑的目标是字符串而非整形。整形可以很容易地划定范围，而字符串变幻莫测，难以预划范围，因此也就无法用严格表结构依赖的动态规划解决。基于这点，我们只能尝试用记忆化搜索来优化暴力递归。 在这之前，先来想想如何对上面的暴力递归进行剪枝。

剪枝可以考虑两个方向：

  1. 尽可能少地进入递归分支。
  2. 尽可能降低递归层数。

在上面的暴力递归中，我们最多只有两个分支，分支数量本身就少，所以可以优先考虑降低递归层数。显然，根据基线条件，target 越早消耗完，递归就会越早结束。那么如何使 target 尽早消耗完呢？不难想到，由于我们是从左往右尝试贴纸的，所以如果将与 target 匹配程度较高的贴纸靠左放，那么 target 贴纸就会更快被拼完。基于这个想法，我们先将 stickers 数组按匹配度排序，再进行暴力递归。代码如下：

//返回sticker和target的字母匹配个数
//比如sticker="helloworld",target="llld"
//则返回4
int containNum(const string &sticker, string target)
{
    int count = 0;
    for (char c : sticker)
    {
        size_t pos = target.find(c);
        if (pos != std::string::npos)
        {
            target.erase(pos, 1);
            count++;
        }
    }
    return count;
}

int minStickerNum(vector<string> stickers, string target)
{
    //使用标准库函数sort进行排序,匹配度高的靠左
    std::sort(stickers.begin(), stickers.end(), [target](const string &a, const string &b){
        return containNum(a, target) > containNum(b, target);
    });
    return process(stickers, target, 0);
}

来看看实际效果：

非排序版本运行时间: 1309227 微秒
排序版本的运行时间:  205253 微秒

效率有明显提升，但提升不大，而且无法通过力扣的代码提交（超时）。

本人多次尝试了分支优化（即能否选择性地进入某个分支），但最终都徒劳而返。下面为该版本加上记忆化搜索。

从左到右-记忆化搜索

int process(const vector<string> &stickers, string target, int index, unordered_map<string, int> &memo)
{
    if(memo.find(target+std::to_string(index)) != memo.end())
        return memo[target+std::to_string(index)];
    if (target.empty())
        return 0;//找到一种选法
    if(index >= stickers.size())//不可置前
        return INT32_MAX; //说明此路径无法凑出target字符
    if(target == minus(stickers[index], target))//不可省略，否则栈溢出
            return process(stickers, target, index + 1, memo);
    int a = process(stickers, target, index + 1, memo);
    string rest = minus(stickers[index], target);
    int b = process(stickers, rest, index, memo);
    int min = std::min(a, b == INT32_MAX ? INT32_MAX : b + 1);
    memo.emplace(target + std::to_string(index), min);
    return min;
}
int minStickerNum4(vector<string> stickers, string target)
{
    std::sort(stickers.begin(), stickers.end(), [target](const string &a, const string &b){
        return containNum(a, target) > containNum(b, target);
    });
    unordered_map<string, int> memo;
    int ret = process(stickers, target, 0, memo);
    return ret == INT32_MAX ? -1 : ret;
}

显然，本递归函数的状态变量是 target 和 index ，所以这里我们将 index 转为字符串后，与 target 拼接在一起作为备忘录的键。

运行结果对比如下：

非排序版本运行时间: 2893688 微秒
排序版本的运行时间: 556259 微秒
记忆化搜索运行时间: 13198 微秒

这次成功通过了力扣的代码提交，但效率不尽人意：

好吧，让我们看看下一个模型能否进一步提高效率。

暴力递归-每种都尝试

int process(std::vector<std::string>& stickers, std::string target)
{
    if (target.empty())
        return 0;
    int min = INT32_MAX;
    for(string s : stickers)
    {
        string rest = minus(s, target);
        if(rest == target)//若此贴纸不包含target所需字母,则尝试直接去下一种贴纸
            continue;
        int ret = process(stickers, rest);
        min = min < ret ? min : ret;
    }
    return min == INT32_MAX ? INT32_MAX : min + 1;
}
int minStickerNum4(std::vector<std::string>& stickers, std::string target) {
    int ans = process(stickers, target);
    return ans == INT32_MAX ? -1 : ans;
}

可见，该版本的递归分支数即为贴纸的数量，时间复杂度太大，也说明有很大的优化空间。从左到右的暴力递归版本和该版本对比如下：

#贴纸数量为25
从左到右版本运行时间: 16517 微秒
每种都尝试的运行时间: 16447604 微秒

从这里我们可以看出，递归分支数（递归广度）比递归深度对时间复杂度的影响更大。

另外，我们发现此递归的状态变量只有 target ，这表明使用记忆化搜索大有可为！

每种都尝试-记忆化搜索

int process4(std::vector<std::string>& stickers, std::string target, unordered_map<string, int> &memo)
{
    if(memo.find(target) != memo.end())
        return memo[target];
    if (target.empty())
        return 0;
    int min = INT32_MAX;
    for(string s : stickers)
    {
        string rest = minus(s, target);
        if(rest == target)
            continue;

        int ret = process(stickers, rest, memo);
        min = min < ret ? min : ret;
    }
    min = min == INT32_MAX ? INT32_MAX : min + 1;
    memo.emplace(target, min);
    return min;
}
int minStickerNum4(std::vector<std::string>& stickers, std::string target)
{
    unordered_map<string, int> memo;
    int ans = process(stickers, target, memo);
    return ans == INT32_MAX ? -1 : ans;
}

它比从左到右模型的记忆化搜索更快，这是因为后者的状态变量为 target 和 index ，两个变量叠加的命中率显然不会高于单个 target 变量的命中率。不过仍有改进空间，让我们继续优化。

暴力递归-每种都尝试-优化

这次优化显然应该优先考虑减少递归分支。如何做到呢？在上面的代码中，当 rest == target ，即此贴纸不包含 target 所需字母时，该分支就会被跳过。换句话说，只要该贴纸包含 target 中的任意一个字符，就会进入递归分支。这样看来，这个“进入”门槛就太低了，因为贴纸很容易就能与 target 产生交集。那么我们想，能不能将门槛提高，更有效地剪掉递归分支呢？可以的，只需将门槛改为以下条件：当该贴纸包含 target 的第 0 个字符时，才能进入递归分支。这样递归分支数就大大减少了。代码如下：

int process(std::vector<std::string>& stickers, std::string target, unordered_map<std::string, int> &memo)
{
    if(memo.find(target) != memo.end())
        return memo[target];
    if (target.length() == 0)
        return 0;
    int min = INT32_MAX;
    for (string s : stickers)
    {
        if(s.find(target[0]) == string::npos)
            continue;
        string rest = minus(s, target);
        if (rest != target)
            min = std::min(min, process(stickers, rest, memo));
    }
    memo.emplace(target, min + (min == INT32_MAX ? 0 : 1));
    return min + (min == INT32_MAX ? 0 : 1);
}

int minStickerNum(std::vector<std::string>& stickers, std::string target) {
    unordered_map<std::string, int> memo;
    int ans = process(stickers, target, memo);
    return ans == INT32_MAX ? -1 : ans;
}

已经可以说是最优解啦！

现在问题是，为什么提高门槛后对答案没有影响？留给读者自己思考（手动狗头）。

总结

  • 本题在动态规划中具有指导地位，它告诉我们不一定非要做到表依赖不可，记忆化搜索+剪枝也能搞出最优解。

  • 剪枝可以考虑两个方向：1）尽可能少地进入递归分支。2）尽可能降低递归层数。

  • 递归分支数（递归广度）比递归深度对时间复杂度的影响更大。

文章作者： 极简
本文链接：
版权声明： 本站所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 后端技术分享！
数据结构与算法
喜欢就支持一下吧