本文涉及知识点

C++动态规划

LeetCode2767. 将字符串分割为最少的美丽子字符串

给你一个二进制字符串 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’ 。

动态规划

can[i][j]记录：s[i][j]是否是5的幂。如果s[i]是0，则一定不是；否则转成整数x，如果x是1，返回true;如果不是5的倍数返回false; x/=5。

动态规划的状态表示

dp[i]表示s的前i个元素能否划分。空间负重度：O(n)

动态规划的填报顺序

枚举前置状态 i = 0 to n-1， j = i to n-1

动态规划的转移方程

如果dp[i] && can[i][j] ,dp[j]成立。

动态规划的初始值

dp[0]=true

动态规划的返回值

dp.back()

代码

核心代码

class Solution {
		public:
			int minimumBeautifulSubstrings(string s) {
				const int N = s.length();
				function<bool(int)> Is = [&](int x) {
					if (0 == x)return false;
					if (1 == x) { return true; }
					if (0 != x % 5)return false;
					return Is(x / 5);
				};
				vector<vector<bool>> can(N, vector<bool>(N));
				for (int i = 0; i < N; i++) {
					int tmp = 0;
					if ('0' == s[i])continue;
					for (int j = i; j < N; j++) {
						tmp = tmp * 2 + (s[j] - '0');
						can[i][j] = Is(tmp);
					}
				}
				vector<int> dp(N + 1, N + 1);
				dp[0] = 0;
				for (int i = 0; i < N; i++) {
					for (int j = i; j < N; j++) {
						if(can[i][j])
						dp[j + 1] = min(dp[j + 1], dp[i] + 1);
					}
				}
				return dp.back() > N ? -1 : dp.back();
			}
		};

单元测试

string s;
		TEST_METHOD(TestMethod11)
		{
			s = "1011";
			auto res = Solution().minimumBeautifulSubstrings(s);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "111";
			auto res = Solution().minimumBeautifulSubstrings(s);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			s = "0";
			auto res = Solution().minimumBeautifulSubstrings(s);
			AssertEx(-1, res);
		}