# 2522. Partition String Into Substrings With Values at Most K
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Greedy`
Link: https://leetcode.com/problems/partition-string-into-substrings-with-values-at-most-k/description/
## 思路
一开始想用dp 但是忽略了k的长度小于等于9的条件 对于每一个i都检查一遍所有在前面的j 因此导致TLE
实际上有更简单的方法就是用greedy track current number ```curr``` 如果```curr>k``` 就开启新的partition
## Code
Greedy

class Solution:
    def minimumPartition(self, s: str, k: int) -> int:
        cur = 0
        ans = 1
        for d in s:
            cur = cur*10+int(d)
            if cur>k:
                ans += 1
                cur = int(d)
            if cur>k:
                return -1
        return ans

DP

class Solution:
    def minimumPartition(self, s: str, k: int) -> int:
        if k<9:
            for d in s:
                if int(d)>k: return -1
        
        dp = [math.inf]*len(s)
        dp[0] = 1
        for i in range(1, len(s)):
            for j in range(max(i-9, -1), i):
                if int(s[j+1:i+1])<=k:
                    dp[i] = min(dp[i], 1 if j==-1 else dp[j]+1)
        return dp[len(s)-1]