【划分型DP-最优划分】力扣2767. 将字符串分割为最少的美丽子字符串

给你一个二进制字符串 s ，你需要将字符串分割成一个或者多个 子字符串 ，使每个子字符串都是 美丽 的。

如果一个字符串满足以下条件，我们称它是 美丽 的：

它不包含前导 0 。
它是 5 的幂的 二进制 表示。
请你返回分割后的子字符串的 最少 数目。如果无法将字符串 s 分割成美丽子字符串，请你返回 -1 。

子字符串是一个字符串中一段连续的字符序列。

示例 1：
输入：s = “1011”
输出：2
解释：我们可以将输入字符串分成 [“101”, “1”] 。

• 字符串 “101” 不包含前导 0 ，且它是整数 51 = 5 的二进制表示。
• 字符串 “1” 不包含前导 0 ，且它是整数 50 = 1 的二进制表示。
  最少可以将 s 分成 2 个美丽子字符串。

示例 2：
输入：s = “111”
输出：3
解释：我们可以将输入字符串分成 [“1”, “1”, “1”] 。

• 字符串 “1” 不包含前导 0 ，且它是整数 50 = 1 的二进制表示。
  最少可以将 s 分成 3 个美丽子字符串。

示例 3：
输入：s = “0”
输出：-1
解释：无法将给定字符串分成任何美丽子字符串。

提示：
1 <= s.length <= 15
s[i] 要么是 ‘0’ 要么是 ‘1’ 。

记忆化搜索

// 预处理 2**15 以内的 5 的幂的二进制表示
vector<string> pow5 = {
    "1", "101", "11001", "1111101", "1001110001", "110000110101", "11110100001001"
};

class Solution {
public:
    int minimumBeautifulSubstrings(string s) {
        int n = s.size();
        vector<int> memo(n, -1);


        function<int(int)> dfs = [&](int i) -> int{
            if(i == n) return 0;
            if(memo[i] != -1) return memo[i];
            if(s[i] == '0') return INT_MAX;

            int res = INT_MAX;
            for(string &t : pow5){
                if(i + t.size() > n) break;
                if(s.substr(i, t.size()) == t){
                    int sub_res = dfs(i + t.size());
                    if(sub_res != INT_MAX){
                        res = min(res, sub_res + 1);
                    }
                }
            }
            return memo[i] = res;
        };
        return dfs(0) == INT_MAX ? -1 : dfs(0);
    }
};

时间复杂度：O(N*K)
空间复杂度: O(N)

我们首先先找出预处理 2^15 以内的 5 的幂的二进制表示，记录在容器pow5中。memo是记忆化用。最重要的是回溯的思路，我们定义dfs(i)的含义是从第i个字符后的字符串被分割成最少的美丽子字符串的个数，所以我们可以思考，我们从第0个字符开始，举个例子，如果找到了一个5的二进制表示101，那么也就是说，在这个回溯中，我们dfs(0)也就是dfs(3)+1，然后dfs(3)会继续往上回溯。那么既然使用了回溯，就要知道在回溯的末端我们该如何处理，在回溯末端我们刚好可以分割完字符串为美丽数组，那么就返回0，也就代表这个回溯的过程是可行的。如果无法分割，还有剩下的字符，那么res依旧为INT_MAX，也就是代表该回溯过程是不可行的。最后返回dfs(0)即可。

原文地址：https://blog.csdn.net/sjsjs11/article/details/143697085

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！