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

链接：2522.将字符串分割成值不超过K的子字符串
难度：Medium
标签：贪心、字符串、动态规划
简介：请你返回 s 所有的 好 分割中，子字符串的 最少 数目。

题解 1 - cpp

• 编辑时间：2023-01-01
• 执行用时：40ms
• 内存消耗：13.3MB
• 编程语言：cpp
• 解法介绍：dp[i]存在 i 个字符的时候最小分割数为 dp[i]。

class Solution {
public:
    int minimumPartition(string s, int k) {
        int n = s.size();
        vector<long long> dp(n + 1, 0x3f3f3f3f);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            long long num = 0;
            for (long long j = i, mul = 1; j >= 1; j--, mul *= 10) {
                num = (s[j - 1] - '0') * mul + num;
                if (num > k) break;
                dp[i] = min(dp[i], dp[j - 1] + 1);
            }
        }
        return dp[n] >= 0x3f3f3f3f ? -1 : dp[n];
    }
};

题解 2 - rust

• 编辑时间：2023-01-01
• 执行用时：12ms
• 内存消耗：3.8MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn minimum_partition(s: String, k: i32) -> i32 {
        let k = k as i128;
        let list = s.as_bytes();
        let n = s.len();
        let mut dp = vec![0x3f3f3f3f_i128; n + 1];
        dp[0] = 0;
        for i in 1..=n {
            let mut num: i128 = 0;
            let mut mul = 1;
            for j in 0..i {
                num = ((list[i - j - 1] as usize - '0' as usize) as i128) * mul + num;
                if num > k {
                    break;
                }
                dp[i] = dp[i].min(dp[i - j - 1] + 1);
                mul *= 10;
            }
        }
        if dp[n] == 0x3f3f3f3f {
            -1
        } else {
            dp[n] as i32
        }
    }
}