本文涉及知识点

C++贪心

LeetCode2522. 将字符串分割成值不超过 K 的子字符串

给你一个字符串 s ，它每一位都是 1 到 9 之间的数字组成，同时给你一个整数 k 。
如果一个字符串 s 的分割满足以下条件，我们称它是一个 好 分割：
s 中每个数位 恰好 属于一个子字符串。
每个子字符串的值都小于等于 k 。
请你返回 s 所有的 好 分割中，子字符串的 最少 数目。如果不存在 s 的 好 分割，返回 -1 。
注意：
一个字符串的 值 是这个字符串对应的整数。比方说，“123” 的值为 123 ，“1” 的值是 1 。
子字符串 是字符串中一段连续的字符序列。
示例 1：
输入：s = “165462”, k = 60
输出：4
解释：我们将字符串分割成子字符串 “16” ，“54” ，“6” 和 “2” 。每个子字符串的值都小于等于 k = 60 。
不存在小于 4 个子字符串的好分割。
示例 2：
输入：s = “238182”, k = 5
输出：-1
解释：这个字符串不存在好分割。
提示：
1 <= s.length <= 10⁵
s[i] 是 ‘1’ 到 ‘9’ 之间的数字。
1 <= k <= 10⁹

动态规划+贪心

n = s.length , str = to_string(k) m = str.length
如果s[0…i]可以拆分成x1个子串和x2个子串，且x1 < x2。某方案将s[0…i]拆分成x2个子串，一定不是最优解。将其拆分成x1个更优。

动态规划的状态表示

dp[i]表示s长度为i的前缀最少可以拆分多少个子串。空间复杂度：O(n）。

动态规划的转移方程

for(int k = 1; (k < m ) && ( i+k <= n );k++)
MinSelf[dp[i+k],dp[i]+1)
如果i+m<=n且s.substr(i,m) <= str则
MinSelf[dp[i+m],dp[i]+1)
空间复杂度：O(nm)

动态规划初始状态

dp[0]=0，其它n+1。

动态规划的顺序

i = 0 To n

动态规划的返回值

dp.back() > n ?-1 :dp.back()

代码

核心代码

class Solution {
		public:
			int minimumPartition(string s, int k) {
				const int N = s.length();
				const string str = to_string(k);
				const int M = str.length();
				vector<int> dp(N + 1,N+1);
				dp[0] = 0;
				for (int i = 0; i < N; i++) {
					for (int k = 1; (k < M) && (i + k <= N); k++) {
						dp[i + k] = min(dp[i + k], dp[i] + 1);
					}
					if ((i + M <= N) && (s.substr(i, M) <= str)) {
						dp[i + M] = min(dp[i + M], dp[i] + 1);
					}
				}
				return (dp.back() > N) ? -1 : dp.back();
			}
		};

单元测试

string s;
		int k;
		TEST_METHOD(TestMethod11)
		{
			s = "165462", k = 60;
			auto res = Solution().minimumPartition(s, k);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "238182", k = 5;
			auto res = Solution().minimumPartition(s, k);
			AssertEx(-1, res);
		}

进一步贪心

dp[i]$\to$ dp[i+x] ，只需要处理最大x。可用决策包容性证明。
字符串比较，可以换成整形。注意：10位数可能会超过int32，故必须用long long。
优化后时间复杂度：O(n)。

再次优化

性质一：第一个子串越长越好，令方案一的长度为n1,方案二的长度为n2,n1<n2。
方案二一定不劣于方案一：第三个子串及后面的子串和方案一完全一样。第二个子串的位数比方案一的第二个子串至少少一位。如果方案一符合，则方案二一定符合。
不断对第一个子串外的字符进行处理$⟺$所有的子串都尽可能的长。

class Solution {
		public:
			int minimumPartition(string s, int k) {
				int ans = 1;
				long long num = 0;
				for (int i = 0; i < s.length(); i++) {
					if (s[i] - '0' > k) { return -1; }
					num = num * 10 + s[i] - '0';
					if (num > k) {
						ans++;
						num %= 10;
					}
				}
				return ans;
			}
		};